1 条题解
-
2
详见注释:
#include <bits/stdc++.h> using namespace std; int n , x , y , t[1005] , s[1005] , maxxn , maxx; /* t保存每个节点的父节点 s保存每个节点的子节点数量 maxxn保存子节点最多的结点编号 maxx保存子节点最多的结点的子节点数量(真绕) f保存此节点是否出现过 */ bool f[1005]; int main() { memset(f , false , sizeof(f));//初始化 scanf("%d" , &n); for (int i = 1 ; i < n ; i++)//看似题目中说输入若干行x和y,实则必定有n-1条数据,因为一个有n个顶点的树必定有n-1条边 { scanf("%d %d" , &x , &y); t[y] = x;//将y的父节点存入数组t //编号为x和y的顶点已出现过 f[x] = true; f[y] = true; //顶点x的子节点数量+1 s[x]++; } //找根节点 for (int i = 1 ; i <= 1000 ; i++) { if (t[i] == 0 && f[i])//i的父亲为0(既没有父亲)而且出现过,只有根节点满足此条件 { printf("%d\n" , i); break;//退出循环 } } //找子节点最多的结点 for (int i = 1 ; i <= 1000 ; i++) { if (s[i] >= maxx) { maxx = s[i]; maxxn = i; } } printf("%d\n" , maxxn); //找到子节点最多的结点的所有子节点 for (int i = 1 ; i <= n ; i++) { if (t[i] == maxxn) printf("%d " , i); } return 0; }
- 1
信息
- ID
- 1184
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 28
- 已通过
- 18
- 上传者