2021-04-05 PAT A1021

测试点1测试的是 整个图只有一个点的时候

#include<cstdio>
#include<set>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10010;
bool vis[maxn];
int father[maxn];
vector<int> graph[maxn];
set<int> ans_A, temp_point;
int find_father(int a) {
    if (a == father[a]) return a;
    return father[a] = find_father(father[a]);
}

void Unite(int a, int b) {
    int fa_a = find_father(a);
    int fa_b = find_father(b);
    if (fa_a != fa_b)
        father[fa_a] = fa_b;
}
int max_height;
void DFS(int u, int height, int pre) {//对算法笔记进行优化，算法笔记上，只要树高大于他，那么就要开始加入vector，但是那么做会损耗很多时间
    if ((graph[u].size() == 1 && graph[u][0] == pre) ||graph[u].size() == 0) {//因为每个点都有回去的点，所以当他等于1的时候，那么就代表着没有点了
        if (height > max_height) {
            temp_point.clear();
            temp_point.insert(u);
            max_height = height;
        }
        else if (height == max_height)temp_point.insert(u);
    }
    else {
        for (int i = 0; i < graph[u].size(); i++) 
            if (graph[u][i] != pre) DFS(graph[u][i], height + 1, u);
    }
}
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) father[i] = i;
    for (int i = 1; i < n; i++) {
        int a, b; scanf("%d %d", &a, &b);
        graph[a].push_back(b), graph[b].push_back(a);
        Unite(a, b);
    }
    int block = 0;
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; i++) {
        int fa = find_father(i);
        if (!vis[fa]) {
            block++;
            vis[fa] = true;
        }
    }
    set<int>::iterator it;
    if (block != 1) printf("Error: %d components\n", block);
    else {
        DFS(1, 1, -1);
        ans_A = temp_point;
        temp_point.clear();
        max_height = 0;
        it = ans_A.begin();
        DFS(*it, 1, -1);
        ans_A.insert( temp_point.begin(), temp_point.end());
    }
    for (it = ans_A.begin(); it != ans_A.end(); it++)printf("%d\n", *it);
}