题目描述

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.

样例1

5
1 2
1 3
1 4
2 5

3
4
5

样例2

5
1 3
1 4
2 5
3 4

Error: 2 components

算法1

采用并查集对整个图的个数进行查找，之后采用dfs对所谓的最深高度的节点进行查找。

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 10001;

int fa[N];
int h[N],e[2*N],ne[2*N],idx;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int find(int x)    //并查集算法
{
    if(fa[x]!=x) fa[x] = find(fa[x]);
    return fa[x];
}
int dfs(int x,int hf)  //dfs寻找最大深度
{
    int depth = 0;
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int t = e[i];
        if(t == hf) continue;
        depth = max(depth,dfs(t,x)+1);
    }
    return depth;
}
int main()
{
    memset(h, - 1, sizeof h);
    int n; cin>>n;
    for(int i=1;i<=n;i++) fa[i]=i;
    int a,b;
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
        int f1 = find(a),f2 = find(b);
        if(f1!=f2)
        {
            fa[f2] = f1;
        }
    }
    int co=0;
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==i) co++;
    }
    if(co>1) printf("Error: %d components",co);
    else{
        vector<int> ans;
        int mdepth=-1;
        for(int i=1;i<=n;i++) 
        {
            int depth = dfs(i,-1); 
            if(depth > mdepth)   //最大深度更新时，要清空原有数组，重新加入元素。
            {
                mdepth = depth;
                ans.clear();
                ans.push_back(i);
            }
            else if(depth==mdepth)
            {
                ans.push_back(i);
            }
        }
        for(auto &x:ans) printf("%d\n",x);
    }
    return 0;
}