1021 Deepest Root (25分)

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 (≤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:

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<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N=10010;

int n;
vector<int> son[N];
vector<int> res;
bool st[N]; 
int p[N];   //并查集 father数组

int find(int x)  //找到x的祖宗结点+路径压缩
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
 } 


int dfs(int u)
{
    int depth=0;
    st[u]=true;  //dfs的时候不能走回头路


    for(int i=0;i<son[u].size();i++)
    {
        if(st[son[u][i]]==true) continue;
        int h=dfs(son[u][i]);
        depth=max(depth,h);
    }

     st[u]=false;
     return depth+1;
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) p[i]=i;

    int k=n;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        son[a].push_back(b);
        son[b].push_back(a);

        if(find(a)!=find(b))
        {
            k--;
            p[find(a)]=find(b);
        }

    }

    if(k>1) printf("Error: %d components", k);
    else
    {

        int max_depth = 0;

        for (int i = 1; i <= n; i ++ )
        {
            int depth = dfs(i);
            if (depth > max_depth)
            {
                max_depth = depth;
                res.clear();    //清空之前小深度的结点
                res.push_back(i);
            }
            else if (depth== max_depth)
                res.push_back(i);
        }

        for (auto v : res) cout << v << endl;
    }

    return 0;
}