close
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
int visit[1001];
int adj[1001][1001];
int main()
{
    queue<int>q;
    int test=0;
    char blank[10];
    int p,d;
    scanf("%d",&test);
    getchar();
    gets(blank);
    while(test--)
    {
        scanf("%d%d",&p,&d);

        for(int i=0; i<p; i++)
        {
            visit[i]=false;
        }
        for(int i=0; i<p; i++)
        {
            for(int j=0; j<p; j++)
            {
                adj[i][j]=false;
            }
        }
        while(d--)
        {
            int temp1,temp2;
            scanf("%d%d",&temp1,&temp2);
            adj[temp1][temp2]=true;
            adj[temp2][temp1]=true;
        }
        int answer[1001]={};
        for(int k=0; k<p; k++)
        {
            if(!visit[k])
            {
                q.push(k);
                visit[k]=true;
                while(!q.empty())
                {
                    int i= q.front();
                    q.pop();
                    for(int j=0; j<p; j++)
                    {
                        if(adj[i][j]&&!visit[j])
                        {
                            q.push(j);
                            visit[j]=true;
                            answer[j]=answer[i]+1;
                            //printf("%d %d %d",j,answer[i],answer[j]);
                        }
                    }
                }
            }
        }
        for(int i=1; i<p; i++)
        {
            printf("%d\n",answer[i]);
        }
        if(test)
        {
            printf("\n");
        }
    }

}
#tree #BFS
arrow
arrow
    文章標籤
    BFS
    全站熱搜

    Nate_Tang 發表在 痞客邦 留言(0) 人氣()