AcWing 1498. 最深的根
原题链接
中等
作者:
YAX_AC
,
2024-11-28 17:25:34
,
所有人可见
,
阅读 5
//graph图 connected有关的,连通的 acyclic无环的 adjacent相邻
//connected components连通分量
//A graph which is connected and acyclic can be considered a tree.
//连通且无环的图可以被视为树
//If such a root is not unique, print them in increasing order of their numbers.
//如果最深的根不唯一,则按照从小到大的顺序
// Now you are supposed to find the root that results in a highest tree
//你要找到可以使得树的高度最大的根节点。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//求连通块的数量--->并查集
//用并查集判断是否只有一个连通块(树)
//是树的话,如何找最深的根,对于每个点做一遍DFS或者BFS,
//如何求最大深度?
//DFS int dfs(u){},求u到叶子节点的最大高度
//讲每个点当作根,每个都求一下树的深度,取最大的那个,不唯一,按升序输出
const int N = 10010,M = N*2;//无向边存两次
int n;
int h[N],e[M],ne[M],idx;
int p[N];
int find(int x)
{
if(p[x]!=x) return p[x] = find(p[x]);
return p[x];
}
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int dfs(int u,int father)
{
int depth = 0;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j==father) continue;//记录父节点,防止走回头路
depth = max(depth,dfs(j,u)+1);//继续往下搜
}
return depth;
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i = 1; 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))//如果不在一个连通块
{
k--;
p[find(a)] = find(b);//讲其连通
}
add(a,b),add(b,a);
}
if(k>1) printf("Error: %d components",k);
else
{
vector<int> ans;
int max_depth = -1;
for(int i = 1; i<=n; i++)
{
int depth = dfs(i,-1);//i前面节点没有,随便记一个数-1
if(depth > max_depth)
{
max_depth = depth;
ans.clear();
ans.push_back(i);
}
else if(depth == max_depth)
ans.push_back(i);
}
for(auto v:ans) cout<<v<<endl;
}
return 0;
}