【例3-1】找树根和孩子
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 365 通过数: 259
【题目描述】
给定一棵树,输出树的根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<bits/stdc++.h>
using namespace std;
int main()
{int n,m,tree[105]={0};cin>>n>>m;int x,y;for(int i=1;i<=m;i++){cin>>x>>y;tree[y]=x;//记录每一个的父亲节点}//寻找根节点int root;for(int i=1;i<=n;i++){if(tree[i]==0){root=i;break;}}cout<<root<<endl;//寻找最大根节点int maxx=0,maxroot;for(int i=1;i<=n;i++){int sum=0;for(int j=1;j<=n;j++){if(tree[j]==i){sum++;}}if(sum>maxx){maxx=sum;maxroot=i;}}cout<<maxroot<<endl;for(int i=1;i<=n;i++)if(maxroot==tree[i]) cout<<i<<" ";return 0;
}