做网站自己买域名山东百搜科技有限公司
1498. 最深的根
- 题目
- 提交记录
- 讨论
- 题解
- 视频讲解
一个无环连通图可以被视作一个树。
树的高度取决于所选取的根节点。
现在，你要找到可以使得树的高度最大的根节点。
它被称为最深的根。
输入格式
第一行包含整数 NN，表示节点数量。
节点编号为 1∼N1∼N。
接下来 N−1N−1 行，每行包含两个整数，表示两个节点之间存在一条边。
输出格式
输出最深的根的节点编号。
如果最深的根不唯一，则按照从小到大的顺序，将它们依次输出，每个占一行。
如果给定的图不是树，输出 Error: K components，其中 KK 是图中连通分量的数量。
数据范围
1≤N≤1041≤N≤104
输入样例1：
5
1 2
1 3
1 4
2 5
输出样例1：
3
4
5
输入样例2：
5
1 3
1 4
2 5
3 4
输出样例2：
Error: 2 components#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N=1e4+10,M=N<<1;
int h[N],e[M],ne[M],idx;
int p[N];
int n;
int find(int x)
{if(p[x]!=x) 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)
{// cout<<u<<endl;int depth=-1;for(int i=h[u];i!=-1;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 cnt=n;for(int i=1;i<=n-1;i++){int x,y;cin>>x>>y;if(find(x)!=find(y))p[find(x)]=find(y),cnt--;add(x,y),add(y,x);}if(cnt>1) {printf("Error: %d components",cnt);return 0;}else{vector<int>node;int maxn=-1;for(int i=1;i<=n;i++){int depth=dfs(i,-1);if(depth>maxn){node.clear();node.push_back(i);maxn=depth;}else if(depth==maxn)node.push_back(i);// cout<<maxn;}for(auto &t:node) cout<<t<<endl;}
}