本文共 1948 字，大约阅读时间需要 6 分钟。

A graph which is connected and acyclic can be considered a tree. The hight 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 (≤10​4​​) 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:

51 21 31 42 5

Sample Output 1:

345

Sample Input 2:

51 31 42 53 4

Sample Output 2:

Error: 2 components

 先利用并查集求有几个集合。。

然后用两遍dfs。。

第一遍dfs任意一个点，求出最大深度点的集合x。。。

第二遍dfs最大深度的任意一个点，求出另一个最大深度点的集合y。。

求两个集合的并集就是题目答案。。。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=10005;int n;int flag=0;int vis[maxn];int len[maxn];int is[maxn];int a[maxn];int Lenn=0;vector
        
         ve[maxn];int Find(int x){ if(x==a[x]) return x; return a[x]=Find(a[x]);}void unit(int x,int y){ int fx=Find(x); int fy=Find(y); if(fx!=fy) a[fx]=fy;}void init(){ memset(vis,0,sizeof(vis)); memset(len,0,sizeof(len)); memset(is,0,sizeof(is));}void dfs (int x,int height){ Lenn=max(Lenn,height); vis[x]=1; len[x]=height; for (int i=0;i
         
          1) printf("Error: %d components\n",flag); else { init(); dfs(1,0); int x; for (int i=1;i<=n;i++) if(len[i]==Lenn) { is[i]=1; x=i; } memset (vis,0,sizeof(vis)); memset (len,0,sizeof(len)); Lenn=0; dfs(x,0); for (int i=1;i<=n;i++) if(len[i]==Lenn) is[i]=1; for (int i=1;i<=n;i++) if(is[i]) printf("%d\n",i); } return 0;}
         
        
       
      
     
    
   

转载地址：http://uxaen.baihongyu.com/