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 (≤104) 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

思路

时间限制2s，很充足，足够每个节点试一次，而不用做什么优化。

再尝试前，记得判断下，联通块的个数。（不然这个25的就太容易过了

代码

#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <limits.h> 
using namespace std;
int N;
vector<int> node[10000 + 10];
int mdeep = INT_MIN;
vector<int> droot;
bool visit[10000 + 10];
int getDeep(int index, int deep){
    //cout << index << endl;
    int mdeep = deep + 1;
    for(int i = 0; i < node[index].size(); i++){
        if(visit[node[index][i]] == false){
            visit[node[index][i]] = true;
            mdeep = max(mdeep, getDeep(node[index][i], deep + 1));
        }
    }
    return mdeep;
}

void dfs(int index){
    for(int i = 0; i < node[index].size(); i++){
        if(visit[node[index][i]] == false){
            visit[node[index][i]] = true;
            dfs(node[index][i]);
        }
    }
}

int getBlock(){
    int block = 0;
    for(int i = 1; i <= N; i++){
        if(visit[i] == false){
            visit[i] = true;
            dfs(i);
            block++; 
        }
    }
    return block;
}

int main() {
    cin >> N;
    int a, b;
    for(int i = 0; i < N - 1; i++){
        cin >> a >> b;
        node[a].push_back(b);
        node[b].push_back(a);
    }
    int block = getBlock();
    if(block != 1){
        cout << "Error: "<< block <<" components" << endl;
        return 0;
    }
    for(int i = 1; i <= N; i++){
        memset(visit, 0, sizeof(visit));
        visit[i] = true;
        int md = getDeep(i, 0);
        if(md > mdeep){
            droot.clear();
            droot.push_back(i);
            mdeep = md;
        }
        else if(md == mdeep){
            droot.push_back(i);
        }
    }
    sort(droot.begin(), droot.end());
    for(int i = 0; i < droot.size(); i++){
        cout << droot[i] << endl; 
    } 
    return 0; 
}