1021. Deepest Root.md

pat 甲级 1021. Deepest Root

题意概述

给定 N 个结点和 N-1 条边，问能否构成一棵树，如果能，则输出作为树的根结点时使得整棵树深度最大的结点，如果不能，输出这个图中有几个连通分量。

输入输出格式

输入第一行都包含一个正整数 N，表示结点的数量，结点的编号从 1 到 N。然后是 N-1 行，每行通过给出两个相邻结点的编号来描述一条边。

在一行中打印所有使得整棵树深度最大的结点。如果这样的结点不是唯一的，按结点编号升序打印。如果给定的图不是树，则打印错误Error: K components，其中 K 是图中的连通分量数。

数据规模

$$N<=10^4$$

算法设计

如果一幅图是一个无环连通图，则该图能构成一棵树。所以要判断给出的图是否是无环连通图，当然这道题降低了难度，因为题目指定了图中有 N 个结点，且只有 N-1 条边，那么如果这幅图是连通的，则必然无环；如果这幅图不连通，则必然有环。所以我们只需判断这幅图是不是连通图即可确认它能不能构成一棵树，关于判断方法，有并查集和深度优先遍历两种方法，我是用了深度优先遍历的方法。

那么如何确定以那一个结点为根时整棵树深度能达到最大呢？可以采用暴力枚举的方法，即求出每一个结点为根时树的深度，然后找到使树的深度最大的根结点即可。求树的深度可以通过一次深度优先遍历得到。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 1e4 + 5;
gg ni;
vector<vector<gg>> graph(MAX);
vector<bool> visit(MAX);
vector<gg> maxDepth(MAX);
gg dfs(gg v) {
    visit[v] = true;
    gg depth = 0;
    for (gg i : graph[v]) {
        if (not visit[i]) {
            depth = max(dfs(i), depth);
        }
    }
    return depth + 1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> ni;
    for (gg i = 1; i < ni; ++i) {
        gg a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    gg num = 0;
    for (gg i = 1; i <= ni; ++i) {
        if (not visit[i]) {
            ++num;
            dfs(i);
        }
    }
    if (num > 1) {
        cout << "Error: " << num << " components\n";
        return 0;
    }
    for (gg i = 1; i <= ni; ++i) {
        fill(visit.begin(), visit.begin() + ni + 1, false);
        maxDepth[i] = dfs(i);
    }
    gg m = *max_element(maxDepth.begin() + 1, maxDepth.begin() + ni + 1);
    for (gg i = 1; i <= ni; ++i) {
        if (maxDepth[i] == m) {
            cout << i << "\n";
        }
    }
    return 0;
}