A题进行时--浙大PAT 1021-1030

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<vector>
 4 #include<queue>
 5 using namespace std;
 6 
 7 #define N 10005
 8 vector<int> v[N];
 9 queue<int> q;
10 int tree[N],h[N],dis[N],vis[N];
11 int n,maxh;
12 
13 int findroot(int x){
14     if(tree[x]==-1)
15         return x;
16     else{
17         int tmp=findroot(tree[x]);
18         tree[x]=tmp;
19         return tmp;
20     }
21 }
22 void merge(int x,int y){
23     x=findroot(x);
24     y=findroot(y);
25     if(x!=y){
26         tree[x]=y;
27     }
28 }
29 int bfs(int p){
30     int height=0;;
31     int i,j,k;
32     while(!q.empty())
33         q.pop();
34     memset(dis,0,sizeof(dis));
35     memset(vis,0,sizeof(vis));
36     q.push(p);
37     vis[p]=1;
38     while(!q.empty()){
39         k=q.front();
40         q.pop();
41         for(i=0;i<v[k].size();i++){
42             if(!vis[v[k][i]]){
43                 dis[v[k][i]]=dis[k]+1;
44                 if(height<dis[v[k][i]])  height=dis[v[k][i]];
45                 q.push(v[k][i]);
46                 vis[v[k][i]]=1;
47             }
48         }
49     }
50     if(maxh<height)
51             maxh=height;
52     return height;
53 
54 }
55 int main(){
56     freopen("in2.txt","r",stdin);
57     int x,y;
58     int i,j;
59     scanf("%d",&n);
60     for(i=0;i<N;i++)
61         tree[i]=-1;
62     for(i=0;i<n;i++){
63         scanf("%d %d",&x,&y);
64         v[x].push_back(y);
65         v[y].push_back(x);
66         merge(x,y);
67     }
68     int cnt=0;
69     maxh=0;
70     for(i=1;i<=n;i++){
71         if(tree[i]==-1)
72             cnt++;
73     }
74     if(cnt==1){
75         for(i=1;i<=n;i++){
76             h[i]=bfs(i);
77         }
78         for(i=1;i<=n;i++){
79             if(h[i]==maxh)
80                 printf("%d\n",i);
81         }
82 
83     }
84     else
85         printf("Error: %d components",cnt);
86 
87     return 0;
88 }