当前位置: 代码迷 >> 综合 >> 【例3-1】找树根和孩子
  详细解决方案

【例3-1】找树根和孩子

热度:85   发布时间:2024-01-15 08:30:00.0

【例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;
}

  相关解决方案