题目描述

一个无环连通图可以被视作一个树。

树的高度取决于所选取的根节点。

现在，你要找到可以使得树的高度最大的根节点。

它被称为最深的根。

输入格式
第一行包含整数 N，表示节点数量。

节点编号为 1∼N。

接下来 N−1 行，每行包含两个整数，表示两个节点之间存在一条边。

输出格式
输出最深的根的节点编号。

如果最深的根不唯一，则按照从小到大的顺序，将它们依次输出，每个占一行。

如果给定的图不是树，输出 Error: K components，其中 K 是图中连通分量的数量

样例

5
1 2
1 3
1 4
2 5


3
4
5

C++ 代码

#include<iostream>
#include<vector>
using namespace std;
const int N=10005;
vector <int> tree[N];
int account=0;
int a,b;
int p[N];//并查集
int find(int aa){//返回该节点的根节点
       if(aa!=p[aa]) p[aa]=find(p[aa]);
       return p[aa];
}

int dfs(int root,int father){//深搜,返回以当前节点为根,树的最大高度
       int max_depth=0;
       for(int i=0;i<tree[root].size();i++){
           if(tree[root][i]==father) continue;
           max_depth=max(max_depth,dfs(tree[root][i],root)+1);
       }
       return max_depth;

}
int main(){
    int account=0;
    int a,b;
    cin>>account;
    int k=account;//连通块数量 
    for(int i=0;i<N;i++){//并查集初始化,每一个元素的父节点都等于它本身
        p[i]=i;
    }
    for(int i=0;i<account-1;i++){     //邻接表建树
    cin>>a>>b;
    if(find(a)!=find(b))//两个结点不在一个连通块内
    {
        p[find(a)]=find(b);
        k--;
    }
    tree[a].push_back(b);  //此为无向边,应添加两条
    tree[b].push_back(a);
    }
    if(k>1)
    printf("Error: %d components\n",k);
    else{
        int root[account+5]={0};
        int max=-99999;
        for(int i=1;i<=account;i++){//对每个节点搜一遍最大深度,并找出最大值
            root[i]=dfs(i,-1);
            if(root[i]>max)
            max=root[i];
        }
        for(int i=1;i<=account;i++){//取最大值输出
            if(root[i]==max)
            cout<<i<<endl;
        }

    }


}