1021.Deepest Root (并查集+DFS树的深度)

A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N-1 lines follow, each describes an edge by given the two adjacent nodes' numbers.

Output Specification:

For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print "Error: K components" where K is the number of connected components in the graph.

Sample Input 1:

1 2

1 3

1 4

2 5

Sample Output 1:

Sample Input 2:

1 3

1 4

2 5

3 4

Sample Output 2:

Error: 2 components

  1 #include <iostream>
  2 
  3 #include <vector>
  4 
  5 #include <queue>
  6 
  7 using namespace std;
  8 
  9 vector<int> adj[10001];
 10 int visit[10001];
 11 int Tree[10001];
 12 int root[10001];
 13 int MM[10001];
 14 int num;
 15 int getroot(int x)
 16 
 17 {
 18 
 19     if(Tree[x]==-1)  return x;
 20 
 21     else
 22 
 23     {
 24         int tem=getroot(Tree[x]);
 25         Tree[x]=tem;
 26         return tem;
 27     }
 28 
 29 }
 30 
 31 
 32 
 33 
 34 
 35 void DFS(int x,int d)
 36 
 37 {
 38     visit[x]=1;
 39     int i;
 40     for(i=0;i<adj[x].size();i++)
 41     {
 42 
 43         if(visit[adj[x][i]]==0) 
 44             DFS(adj[x][i],d+1);
 45     }
 46     root[num++]=d;
 47 }
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 int main()
 58 
 59 {
 60     int n,a,b,i,j;
 61     while(cin>>n)
 62     {
 63         for(i=1;i<=n;i++)//初始化
 64         {
 65             Tree[i]=-1;
 66             adj[i].clear();
 67         }
 68         for(i=0;i<n-1;i++)
 69         {
 70             cin>>a>>b;
 71             adj[a].push_back(b);
 72             adj[b].push_back(a);
 73             a=getroot(a);//并查集
 74             b=getroot(b);
 75             if(a!=b)
 76             {
 77                 Tree[a]=b;
 78             }
 79         }
 80         int count=0;//极大连通图个数
 81         for(i=1;i<=n;i++)
 82         {
 83             if(Tree[i]==-1) count++;
 84         }
 85         if(count!=1)
 86         {
 87             cout<<"Error: "<<count<<" components"<<endl;//不是树
 88         }
 89         else
 90         {
 91             for(i=1;i<=n;i++)
 92             {
 93                 for(j=1;j<=n;j++)//每次查找都要初始化
 94                     visit[j]=0;
 95                 num=0;
 96                 DFS(i,1);
 97                 MM[i]=0;
 98                 for(j=0;j<num;j++)
 99                 {
100                     if(MM[i]<root[j])
101                         MM[i]=root[j];
102                 }
103             }
104             int max=0;
105             for(i=1;i<=n;i++)
106             {
107                 if(max<MM[i])
108                     max=MM[i];
109             }
110             for(i=1;i<=n;i++)
111             {
112                 if(max==MM[i])
113                     cout<<i<<endl;
114             }
115         }
116     }
117     return 0;
118 }