首页 > 代码库 > 找树的根和孩子

找树的根和孩子

2024-10-27 06:45:02   211人阅读

【问题描述】
　　给定一棵树，输出树的根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

【参考程序】

 1 #include<iostream>
 2 using namespace std;
 3 int n,m,tree[101]={0};
 4 int main()
 5 {
 6   int i,x,y,root,maxroot,sum=0,j,Max=0;
 7   cin>>n>>m;
 8   for(i=1;i<=m;i++)
 9   {
10     cin>>x>>y;
11     tree[y]=x;
12   }
13   for(i=1;i<=n;i++)                     //找出树根 
14      if(tree[i]==0)
15      {
16         root=i;break;
17      }
18   for(i=1;i<=n;i++)                     //找孩子最多的结点
19   {
20      sum=0; 
21      for(j=1;j<=n;j++)
22         if(tree[j]==i) sum++;
23      if(sum>Max)
24      {
25          Max=sum;maxroot=i;
26      }
27   }    
28   cout<<root<<endl<<maxroot<<endl;  
29   for(i=1;i<=n;i++)
30      if(tree[i]==maxroot) cout<<i<<" ";
31   return 0; 
32 }

 

找树的根和孩子


联系
我们