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:

5

1 2

1 3

1 4

2 5

 Sample Output 1:

3

4

5

 Sample Input 2:

5

1 3

1 4

2 5

3 4

 Sample Output 2:

Error: 2 components

 

1 #include 
     
        2   3 #include 
      
         4   5 #include 
       
          6   7 using namespace std;  8   9 vector
        
          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
         
          >n) 62     { 63         for(i=1;i<=n;i++)//初始化 64         { 65             Tree[i]=-1; 66             adj[i].clear(); 67         } 68         for(i=0;i
          
           >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: "<
           
            <<" components"<