哈尔滨网站建立公司,少儿编程线下培训机构排名前十,提交网址,软件技术主修课程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;}
}
