1021 Deepest Root (25 分)（并查集，dfs，连通分量个数）

 1 #pragma warning(disable:4996)
 2 #define _CRT_SECURE_NO_WARNINGS
 3 
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <unordered_set>
11 #include <unordered_map>
12 #include <queue>
13 #include <cmath>
14 #include <string>
15 #define INFINITE 65535
16 #define mod 1000000007
17 using namespace std;    
18 vector<int> edge[10010], maxd;
19 int depth = 0;
20 int vis[10010] = { 0 };
21 void dfs(int s, int dep)
22 {
23     vis[s] = 1;
24     if (dep > depth)depth = dep;
25     for (int i = 0; i < edge[s].size(); ++i){
26         if (!vis[edge[s][i]]){
27             dfs(edge[s][i], dep + 1);
28         }
29     }
30 }
31 int main()
32 {
33     int n;
34     cin >> n;
35     maxd.resize(n+1);
36     for (int i = 0; i < n - 1; ++i){
37         int a, b;
38         cin >> a >> b;
39         edge[a].push_back(b);
40         edge[b].push_back(a);
41     }
42     int max = 0;
43     int num = 0;
44     for (int i = 1; i <= n; ++i){
45         fill(vis, vis + 10010, 0);
46         depth = 0;
47         dfs(i, 0);    
48         maxd[i] = depth;
49         if (depth > max)max = depth;
50     }
51     fill(vis, vis + 10010, 0);
52     for (int i = 1; i <= n; ++i){
53         if (!vis[i]) {
54             ++num;
55             dfs(i, 0);
56         }
57     }
58     vector<int> res;
59     if (num == 1) {
60         for (int i = 1; i <= n; ++i)
61             if (maxd[i] == max)
62                 res.push_back(i);
63         for (int it : res)
64             cout << it << endl;
65     }
66     else{
67         cout << "Error: "<< num <<" components"<< endl;
68     }
69     return 0;
70 }

 1 #pragma warning(disable:4996)
 2 #define _CRT_SECURE_NO_WARNINGS
 3 
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <unordered_set>
11 #include <unordered_map>
12 #include <queue>
13 #include <cmath>
14 #include <string>
15 #define INFINITE 65535
16 #define mod 1000000007
17 using namespace std;    
18 vector<int> edge[10010], maxd, father;
19 int depth = 0;
20 int vis[10010] = { 0 };
21 int findRoot(int i)
22 {
23     if (father[i] == i) {
24         return i;
25     }
26     int temp = findRoot(father[i]);
27     father[i] = temp;//压缩路径
28     return temp;
29 }
30 void unionSet(int a, int b)
31 {
32     int ra = findRoot(a);
33     int rb = findRoot(b);
34     if (ra != rb) {
35         father[ra] = rb;
36     }
37 }
38 void dfs(int s, int dep)
39 {
40     vis[s] = 1;
41     if (dep > depth)depth = dep;
42     for (int i = 0; i < edge[s].size(); ++i) {
43         if (!vis[edge[s][i]]) {
44 
45             unionSet(s, edge[s][i]);
46             dfs(edge[s][i], dep + 1);
47         }
48     }
49 }
50 int main()
51 {
52     int n;
53     cin >> n;
54     maxd.resize(n + 1); father.resize(n + 1);
55     for (int i = 1; i <= n; ++i) father[i] = i;
56     for (int i = 0; i < n - 1; ++i){
57         int a, b;
58         cin >> a >> b;
59         edge[a].push_back(b);
60         edge[b].push_back(a);
61     }
62     int max = 0;
63     int num = 0;
64     for (int i = 1; i <= n; ++i){
65         fill(vis, vis + 10010, 0);
66         depth = 0;
67         dfs(i, 0);    
68         maxd[i] = depth;
69         if (depth > max)max = depth;
70     }
71     for (int i = 1; i <= n; ++i) {
72         if (father[i] == i)++num;
73     }
74     if (num == 1) {//全部结点连通
75         vector<int> res;
76         for (int i = 1; i <= n; ++i)
77             if (maxd[i] == max)
78                 res.push_back(i);
79         for (int it : res)
80             cout << it << endl;
81     }
82     else{
83         cout << "Error: "<< num <<" components"<< endl;
84     }
85     return 0;
86 }