先用dfs数出图的连通分量数count
,如果连通分量数count > 1
直接输出结果;
如果count == 1
,说明该图连通,又因为图中只有n - 1
条边,该图必然为无环图,对每个根节点进行dfs,找出根的最大深度。
#include<cstdio>
#include<unordered_set>
#include<vector>
#include<set>
using namespace std;
int n;
unordered_set<int> map[10001];
bool visited[10001];
void dfs(int cur) {
visited[cur] = true;
for (int e : map[cur]) {
if (!visited[e])
dfs(e);
}
}
int countComponent() {
int count = 0;
for (int i = 1;i <= n;i++) {
if (!visited[i]) {
dfs(i);
count++;
}
}
return count;
}
int maxDepth = 0, source;
set<int> res;
void findDeepest(int cur, int depth) {
visited[cur] = true;
bool hasMoreVertex = false;
for (int e : map[cur]) {
if (!visited[e]) {
hasMoreVertex = true;
findDeepest(e, depth + 1);
}
}
if (!hasMoreVertex) {
if (depth > maxDepth) {
res.clear();
maxDepth = depth;
res.insert(cur);
res.insert(source);
}
else if (depth == maxDepth) {
res.insert(cur);
res.insert(source);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 0;i < n - 1;i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
map[v1].insert(v2);
map[v2].insert(v1);
}
int count = countComponent();
if (count == 1) {
for (int i = 1;i <= n;i++) {
if (map[i].size() > 1 || res.find(i) != res.end())
continue;
fill(visited, visited + 10001, false);
source = i;
findDeepest(i, 0);
}
for (int e : res)
printf("%d\n", e);
}
else printf("Error: %d components\n", count);
}