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
文章標籤
全站熱搜