外贸网站推广方法,毕业设计指导网站开发,重庆网站建设挑夹夹虫,可以兼职做设计的网站1498. 最深的根 题目 提交记录 讨论 题解 视频讲解 一个无环连通图可以被视作一个树。
树的高度取决于所选取的根节点。
现在#xff0c;你要找到可以使得树的高度最大的根节点。
它被称为最深的根。
输入格式
第一行包含整数 NN#xff0c;表示节点数量。
节点…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 N1e410,MN1;
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)
{// coutuendl;int depth-1;for(int ih[u];i!-1;ine[i]){int je[i];if(jfather) continue;depthmax(depth,dfs(j,u)1);}return depth;
}
int main()
{cinn;memset(h,-1,sizeof(h));for(int i1;in;i) p[i]i;int cntn;for(int i1;in-1;i){int x,y;cinxy;if(find(x)!find(y))p[find(x)]find(y),cnt--;add(x,y),add(y,x);}if(cnt1) {printf(Error: %d components,cnt);return 0;}else{vectorintnode;int maxn-1;for(int i1;in;i){int depthdfs(i,-1);if(depthmaxn){node.clear();node.push_back(i);maxndepth;}else if(depthmaxn)node.push_back(i);// coutmaxn;}for(auto t:node) couttendl;}
}
