1021 Deepest Root （25 分）（樹的周遊）

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:

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
           

分析：

本題考查樹的周遊，具體的做法是：在判斷連通圖的個數過程中，将deeproot收集到set中，然後當圖隻有一個連通域時，任選set中一個點作為root，一次深度優先周遊，收集deeproot，做兩次dfs後合并的deeproot即為題目要求的root

注：開始的時候錯誤進行了1+x2次（x是第一次收集的節點數）,導緻測試點逾時，其實隻需在第一次收集的節點中任選一個節點，進行dfs即可找出是以deeproot。因為第一次收集的節點間位置是等價的。

#include <iostream> 
#include <set> 
#include <vector> 

using namespace std;
const int inf=99999;
set<int> ans,ans1,ans2;
int maxheight=-1;
int n;
vector<vector<int> > v;
vector<bool> visit;
void dfs(int u,int height){
    visit[u]=true;
    if(height>maxheight){
        ans.clear();
        ans.insert(u);
        maxheight=height;
    }else if(height==maxheight){
        ans.insert(u);
    }
    for(int i=0;i<v[u].size();i++){
        if(!visit[v[u][i]]) dfs(v[u][i],height+1);
    }
}
int main(){ 
    int cnt=0;
    scanf("%d",&n); 
    v.resize(n+1),visit.resize(n+1);
    for(int i=1;i<=n-1;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(!visit[i]) {
            dfs(i,0);
            cnt++;
        }
    }
    if(cnt!=1){
        printf("Error: %d components",cnt);
        return 0;
    }
    ans2=ans;
    maxheight=-1;
    fill(visit.begin(),visit.end(),false);
    ans.clear();
    dfs(*(ans2.begin()),0);
    for(auto k : ans) ans2.insert(k);
    for(auto it : ans2) printf("%d\n",it);
    return 0;
}