1021 Deepest Root (25)（25 分）

1021 Deepest Root (25)（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 (<=10000) 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:

Sample Output 1:

3
4
5

Sample Input 2:

Sample Output 2:

Error: 2 components

题意：
给出n个节点（1~n），并给出n-1个边，求图的连通分量。如果连通分量为1，则求图对应的树的最大深度对应的root，如果不唯一则按升序排列输出。

思路：
柳婼の blog
1.先通过DFS判断图的连通分量个数。
2.任取一个顶点，DFS求得最高高度的结点们，然后从中任取一个结点，再做一个DFS求得最高高度的结点们，做一个并集得到最终结果。

题解：

#include<cstdio>
#include<vector>
#include<set>
using namespace std;
vector<vector<int>> mp;
bool isVisit[10010];
int maxHeight = 1;
vector<int> temp;
set<int> s;
void dfs(int node, int height) {
    if (height > maxHeight) {
        temp.clear();
        temp.push_back(node);
        maxHeight = height;
    }
    else if (height == maxHeight) { 
        temp.push_back(node);
    }
    isVisit[node] = true;
    for (int i = 0; i < mp[node].size(); i++) {
        if (isVisit[mp[node][i]] == false) {
            dfs(mp[node][i], height + 1);
        }
    }
}
int main() {
    int n;
    scanf("%d", &n);
    mp.resize(n + 1);
    int a, b;
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &a, &b);
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    int cnt = 0;
    int s1;
    for (int i = 1; i <= n; i++) {
        if (isVisit[i] == false) {
            dfs(i, 1);
            //假设cnt为1，将temp中的值放入s中。
            //如果cnt>1，这些值虽然不对，但也没用上。
            if (i == 1) {
                if (temp.size() != 0) s1 = temp[0];
                for (int j = 0; j < temp.size(); j++) {
                    s.insert(temp[j]);
                }
            }
            cnt++;
        }
    }
    if (cnt >= 2) {
        printf("Error: %d components\n", cnt);
    }
    else {
        temp.clear();
        fill(isVisit, isVisit + 10010, false);
        dfs(s1, 1);
        for (int i = 0; i < temp.size(); i++) {
            s.insert(temp[i]);
        }
        for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
            printf("%d\n", *it);
        }
    }
    return 0;
}

1021 Deepest Root (25)（25 分）

推荐阅读更多精彩内容