时间限制: 1000 ms 内存限制: 65536 KB 提交数: 2511 通过数: 1325
【题目描述】给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子。
【输入】第一行：n（结点个数≤100），m（边数≤200）。
以下m行：每行两个结点x和y，表示y是x的孩子(x,y≤1000)。
【输出】第一行：树根：root；
第二行：孩子最多的结点max；
第三行：max的孩子（按编号由小到输出）。
【输入样例】8 7 4 1 4 2 1 3 1 5 2 6 2 7 2 8
【输出样例】4 2 6 7 8
【来源】No
代码#include using namespace std; int n,m,tree[101]={0}; int main () { int i,j,x,y,root,maxroot,sum=0,Max=0; cin>>n>>m; for(i=1;i<=m;i++) { cin>>x>>y; tree[y]=x; } for(i=1;i<=n;i++) { if(tree[i]==0) { root=i; break; } } for(i=1;i<=n;i++) { sum=0; for(j=1;j<=n;j++) { if(tree[j]==i) sum++; } if(sum>Max) { Max=sum; maxroot=i; } } cout<<root<<endl<<maxroot<<endl; for(i=1;i<=n;i++) { if(tree[i]==maxroot) cout<<i<<' '; } return 0; }
代码分析
for(i=1;i<=m;i++) { cin>>x>>y; tree[y]=x; }
读入数据，因为树的特点：每一个节点都只有唯一的前驱元素，所以用数组来的存储每个子节点的父节点。
for(i=1;i<=n;i++) { if(tree[i]==0) { root=i; break; } }
找出根节点，根节点肯定没有父节点，所以父节点为0的点就是根节点。
for(i=1;i<=n;i++) { sum=0; for(j=1;j<=n;j++) { if(tree[j]==i) sum++; } if(sum>Max) { Max=sum; maxroot=i; } }
找出孩子最多的节点，首先二重循环遍历所有的节点，如果某个子结点存储的父节点等于一层循环遍历的数，说明二层循环遍历的数是一层循环遍历的数的父节点，子节点数++，最大的节点为maxroot。
cout<<root<<endl<<maxroot<<endl; for(i=1;i<=n;i++) { if(tree[i]==maxroot) cout<<i<<' '; }
打印结果，如果父节点为maxroot，则子结点为最多的那个。
