1021 Deepest Root

---

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

---

题目大意

给定一个无向图，判断其是否能构成一棵树。如果不能，输出其连通分量的个数；如果能，求构成最大深度树时的根节点，如果该节点不唯一，降序输出。

---

思路

查并集求得连通分量个数，不唯1不是树。

将所有节点间连通数量为一的节点，选入DFS暴力判断

依次求得最大深度即可

ps: 注意N=1的情况

---

C/C++ 

#include
using namespace std;
vector<int> road[10001];
int N,a,b;
bool appear[10001];
void findUnion(int now); // 查并集
void findDeep(int now,int deep,int *maxDeep); // 寻找最大的深度
int main()
{
    cin >> N;
    for(int z=1;z
        cin >> a >> b;
        road[a].push_back(b);
        road[b].push_back(a);
    }
    vector<int> keys,result;
    int flag = 0;
    for(int z=1;z<=N;z++){
        if(road[z].size()==1) keys.push_back(z);
        if(appear[z]) continue;
        findUnion(z);
        flag++;
    }
 
    if(N==1) cout << 1 << endl;
    else if(flag>1) printf("Error: %d components\n",flag);
    else
    {
        memset(appear,0,sizeof appear);
        int deepKey=0,maxDeep;
        for(int x:keys){
            maxDeep = 0;
            findDeep(x,1,&maxDeep);
            if(maxDeep>deepKey) result.clear(),deepKey = maxDeep;
            if(maxDeep==deepKey) result.push_back(x);
        }
        for(int x:result) cout << x << endl;
    }
    return 0;
}
void findUnion(int now){
    if(appear[now]) return;
    appear[now] = true;
    for(int x:road[now]) findUnion(x);
}
void findDeep(int now,int deep,int *maxDeep){
    if(appear[now]) return;
    appear[now] = true;
    *maxDeep = max(*maxDeep,deep);
    for(int x:road[now]) findDeep(x,deep+1,maxDeep);
    appear[now] = false;
}

---