使用暴搜, 数据范围$10^4$, 时间复杂度为$O(n^2)$, 在1s内能通过
本题核心: 先使用并查集维护连通分量 再使用dfs对每个点都进行暴搜
注意: 无向图的dfs 关于是否走回头路的处理方式
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
// 无向图 需要存两条边
const int N = 10010, M = 2 * N;
// 注意e ne是邻接表 h是顶点表 需要的空间不同
int h[N], e[M], ne[M], idx;
int n;
int p[N]; // 并查集 需要的path数组
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 核心 u表示当前结点 father表示父节点,防止走回头路
int dfs(int u, int father){
int depth = 0; // 0 1都可以 这里目的是求满足最大深度的结点编号
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i]; // 遍历所有子节点(出边)
if(j == father) continue; // 不能走回头路
depth = max(depth, dfs(j, u) + 1); // 子节点暴搜 但父节点深度大1
}
return depth; // 返回当前结点深度
}
int main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n; i++) p[i] = i;
int k = n; // 初始化时 连通分量的个数
for(int i = 0; i < n-1; i++){
int a, b;
cin >> a >> b;
if(find(a) != find(b)){ // 没有环则连通分量数-1
k--;
p[find(a)] = find(b);
}
add(a, b), add(b, a); // 无向图 需要插入双向的边
}
if(k > 1){
printf("Error: %d components", k);
}else{
vector<int> nodes; // 开一个vector存储结果
int max_depth = -1;
for(int i = 1; i <= n; i++){
int depth = dfs(i, -1);
if(depth > max_depth){ // 最大深度更新,把之前的存储结果倒掉
max_depth = depth;
nodes.clear();
nodes.push_back(i); // 插入更深一层的结点
}
else if(depth == max_depth){
nodes.push_back(i);
}
}
for(auto node : nodes){
cout << node << endl;
}
}
return 0;
}