1021 Deepest Root（树的直径、bfs/dfs、并查集）

 先通过并查集判断有几个连通图，如果只有一张图，那就用两次dfs/bfs来找到树的直径上的所有端点

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 vector<int> edges[10005];
 5 bool visited[10005] = {false};
 6 set<int> temp; //记录该次dfs筛选出树直径上的端点
 7 set<int> res; //所有树直径上的端点
 8 vector<int> parents(10005); //父节点，用于并查集
 9 int maximum = -1;
10 int find(int x) {
11     if (x == parents[x]) {
12         return x;
13     }
14     parents[x] = find(parents[x]); //路径压缩
15     return parents[x];
16 }
17 void merge(int a, int b) {
18     int pa = find(a);
19     int pb = find(b);
20     if (pa != pb) {
21         parents[pb] = pa;
22     }
23 }
24 
25 void dfs(int p, int level) {
26     if (level > maximum) {
27         temp.clear();
28         temp.insert(p);
29         maximum = level;
30     } else if (level == maximum) {
31         temp.insert(p);
32     }
33     visited[p] = true;
34     for (auto i : edges[p]) {
35         if (!visited[i]) {
36             dfs(i, level + 1);
37         }
38     }
39 }
40 int main() {
41     cin >> n;
42     int a, b;
43     for (int i = 1; i <= n; ++ i) {
44         parents[i] = i;
45     }
46     for (int i = 0; i < n - 1; ++ i) {
47         cin >> a >> b;
48         edges[a].push_back(b);
49         edges[b].push_back(a);
50         merge(a,b);
51     }
52     int components = 0;
53     for (int i = 1; i <= n; ++ i) {
54         if (find(i) == i) {
55             components ++;
56         }
57     }
58     if (components > 1) {
59         printf("Error: %d components", components);
60         return 0;
61     }
62     int root = 1;
63     dfs(root, 0); //第一次dfs用于找到树直径上的端点
64     for (auto i : temp) {
65         res.insert(i);
66         root = i; //取任意一个树直径上的端点
67     }
68     memset(visited, false, sizeof(visited));
69     temp.clear();
70     dfs(root, 0); //以树直径上的端点为根进行遍历，得到所有树直径上的端点
71     for (auto i : temp) {
72         res.insert(i);
73     }
74     for (auto i : res) {
75         cout << i << endl;
76     }
77 
78 }