PAT-A 1021 Deepest Root (25)

#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e4 + 5;

vector<int> G[mxN], tmp;  // 无向图, 临时解集
vector<bool> vis(mxN);

int max_h = 0;

void dfs(int idx, int h) {
    vis[idx] = true;
    if (h > max_h) {
        max_h = h;
        tmp.clear();
        tmp.push_back(idx);
    } else if (h == max_h) {
        tmp.push_back(idx);
    }

    // 搜索当前结点所有子结点
    for (auto it = G[idx].begin(); it != G[idx].end(); it++) {
        if (vis[*it]) continue;
        dfs(*it, h + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 1; i < N; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int K = 0;  // 统计连通分量
    for (int i = 1; i <= N; i++) {
        if (!vis[i]) {
            dfs(i, 0);
            K++;
        }
    }

    if (K > 1) {  // 连通分量大于 1, 非连通图, 输出错误
        cout << "Error: " << K << " components" << endl;
        return 0;
    }

    // 保存第一次深搜的解集
    set<int> ans(tmp.begin(), tmp.end());

    // 第二次深搜
    fill(vis.begin(), vis.begin() + N + 1, false);
    dfs(tmp[0], 0);

    // 保存第二次深搜的解集
    for (auto it = tmp.begin(); it != tmp.end(); it++) {
        ans.insert(*it);
    }
    for (auto it = ans.begin(); it != ans.end(); it++) {
        cout << *it << endl;
    }
}