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

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

vector<int> adj[10001];

int visit[10001];

int Tree[10001];

int root[10001];

int MM[10001];

int num;

int getroot(int x)

{

   if(Tree[x]==-1)  return x;

   else

   {

      int tem=getroot(Tree[x]);

        Tree[x]=tem;

        return tem;

   }

}

void DFS(int x,int d)

{

      visit[x]=1;

    int i;

   for(i=0;i<adj[x].size();i++)

   {

     if(visit[adj[x][i]]==0) 

            DFS(adj[x][i],d+1);

   }

   root[num++]=d;

}

int main()

{

      int n,a,b,i,j;

      while(cin>>n)

      {

                  for(i=1;i<=n;i++)//初始化

                  {

                      Tree[i]=-1;

                        adj[i].clear();

                  }

            for(i=0;i<n-1;i++)

            {

                cin>>a>>b;

                  adj[a].push_back(b);

                  adj[b].push_back(a);

                  a=getroot(a);//并查集

                  b=getroot(b);

                  if(a!=b)

                  {

                     Tree[a]=b;

                  }

            }

            int count=0;//极大连通图个数

                  for(i=1;i<=n;i++)

                  {

                     if(Tree[i]==-1) count++;

                  }

                  if(count!=1)

                  {

                     cout<<"Error: "<<count<<" components"<<endl;//不是树

                  }

                  else

                  {

                       for(i=1;i<=n;i++)

                        {

                                for(j=1;j<=n;j++)//每次查找都要初始化

                                 visit[j]=0;

                                 num=0;

                               DFS(i,1);

                                 MM[i]=0;

                                 for(j=0;j<num;j++)

                                 {

                                      if(MM[i]<root[j])

                                            MM[i]=root[j];

                                 }

                        }

                        int max=0;

                        for(i=1;i<=n;i++)

                        {

                            if(max<MM[i])

                                    max=MM[i];

                        }

                for(i=1;i<=n;i++)

                        {

                            if(max==MM[i])

                                    cout<<i<<endl;

                        }

                  }

      }

   return 0;

}

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