做网站自己买域名网页制作与网站建设实战教程

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;}
}