Pat 1498 求树最深的根

题目

一个无环连通图可以被视作一个树。

树的高度取决于所选取的根节点。

现在，你要找到可以使得树的高度最大的根节点。

它被称为最深的根。

输入格式

第一行包含整数 N，表示节点数量。

节点编号为 1∼N。

接下来 N−1 行，每行包含两个整数，表示两个节点之间存在一条边。

输出格式

输出最深的根的节点编号。

如果最深的根不唯一，则按照从小到大的顺序，将它们依次输出，每个占一行。

如果给定的图不是树，输出 Error: K components，其中 K 是图中连通分量的数量。

数据范围

$1 \le N \le 10^4$

输入样例1：

5
1 2
1 3
1 4
2 5

输出样例1：

3
4
5

输入样例2：

5
1 3
1 4
2 5
3 4

输出样例2：

Error: 2 components

题解

1. 

    // 数据结构：无向图存两条有向边
    vector<int> graph[N];   // 图的临接表存储
    for(int i = 1; i < node_count; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);      // 无向图存两条边
        graph[b].push_back(a);
    }
        
    // 判断是否只有一个连通分量（connected components in the graph）
    // 并查集
    // BFS / DFS 每次遍历结束要查看是否还有没访问的边，调用BFS/DFS的次数就是连通分量数
    bool visited[N];
    bool check_connected()
    {
        memset(visited, false, sizeof(visited));	// #include <cstirng>
        int component = 0;
        for(int i = 1; i <= node_count; i++) {
            if (!visited[i]) {
                component++;
                visit(i, -1);
            }
        }
        return component == 1;
    }
        
    void visit(int node, int father)
    {
        visited[node] = true;
        for(int n : graph[node]) {
            if (n == father) continue;
            if (visited[n]) continue;
            visit(n, node);
        }
    }
        
    // 枚举所有的点，找到最大深度的顶点。
    vector<int> max_depth_root;
    int max_depth = 0;
    for(int i = 1; i <= node_count; i++) {
        int depth = cal_max_depth(i, -1);
        
        if (depth > max_depth) {
              max_depth = depth;
              max_depth_root.clear();
              max_depth_root.push_back(i);
        } else 
        if(depth == max_depth) {
              max_depth_root.push_back(i);
        }
    }
        
    int cal_max_depth(int root, int father)
    {
        int depth = 0;
        for(int n : graph[root]) {
            if (n == father) continue;
            depth = max(depth, cal_max_depth(n, root) + 1);
        }
        return depth;
    }