1 条题解
-
0
#include<bits/stdc++.h> using namespace std; int n; // [1] n-树的节点总数(编号1~n) int arr[110]; // [2] arr数组-存储每个节点的父节点(下标为节点编号,值为父节点编号) // 递归函数:查找节点c的根节点(根节点的父节点是自身) int f(int c){ if(arr[c] == c) return c; // [3] 如果当前节点c的父节点是自己,说明它就是根节点,直接返回 else return f(arr[c]); // [4] 否则递归向上查找父节点的根节点 } int main(){ cin>>n; // [5] 读取节点总数n // 初始化:假设每个节点的父节点是自己(根节点最终会满足arr[c]==c) for(int i=1;i<=n;i++) arr[i]=i; // [6] 初始化父节点数组,每个节点初始父节点为自身 // 读入n-1对父子关系,更新子节点的父节点 int a,b; for(int i=1;i<n;i++){ cin>>a>>b; arr[b]=a; // [7] 输入X(a)是Y(b)的父节点,所以设置节点b的父节点为a } // 对每个节点,找到它的根节点(并更新arr[i]为根节点,实现路径压缩) for(int i=1;i<=n;i++){ arr[i]=f(arr[i]); // [8] 调用f函数找到节点i的根节点,并更新arr[i]为根节点 } // 输出根节点(所有节点的根节点都相同,所以输出arr[1]即可) cout<<arr[1]; // [9] 输出树的根节点编号 return 0; }
- 1
信息
- ID
- 1065
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者