# Congratulations on seeing this solution. It will help you avoid many pitfalls

Of course, I don't want the big guy to be like the big guy in the following question. [AHOI2017/HNOI2017] big man - Luoguhttps://www.luogu.com.cn/problem/P3724
1336: [example 3-1] find tree roots and children

Time limit: 1000 ms memory limit: 65536 KB
Number of submissions: 12616 number of passes: 6521

### [Title Description]

Given a tree, the root of the output tree, the node max with the most children and his children.

### [input]

The first line: n (number of nodes ≤ 100 ≤ 100), m (number of sides ≤ 200 ≤ 200).

The following m lines: each line has two nodes X and y, indicating that y is the child of X (x,y ≤ 1000x,y ≤ 1000).

### [output]

The first line: root;

The second line: node max with the most children;

The third line: max's children (output from small to small by number).

```8 7
4 1
4 2
1 3
1 5
2 6
2 7
2 8```

### [output example]

```4
2
6 7 8```

If you meet someone in the examination room, the exam must be very watery (wonderful)

# This problem is the basic example of the tree, but there are three bug s

No more nonsense, start now!!!

Because a root here may have many nodes, so... It's coming, it's coming

Structure array!!!

The code snippet is as follows:

```struct node{
int data;//numerical value
}a[101];//node```

Define n,m,root,max,x,y in the title (write the input by the way)

```int n,m,x,y,root,maxx=-1;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>x>>y;
a[x].data=y;
}```

## First bug:

Only a[y] can exist here. The father is x (very strange)

```int n,m,x,y,root,maxx=-1;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>x>>y;
a[y].data=x;
}```

## Second bug:

If x or y exceeds n, there is no solution to this problem!!!

Next step: find the father and find the root node. The root node has no father node. Then (we set the data of the root node to x): a [x] data=0

You might as well pass the second bug and a [x] Data = 0 can infer the following code segment:

```for(int i=0;i<n;i++)
{
if(a[i].data==0)
{
root=i;
break;
}
}
cout<<root<<endl;```

Isn't it simple?

Next, let's count max

Make a sum and take the larger value for each comparison

Nested loop. If the data of the inner father is the outer, sum++

(it's a little hard to understand. If you don't understand, you can write it in the chat area, but the author doesn't often come to CSDN. If you don't understand, you can think more for a while. You really can't mention it again, ok?)

The code snippet is as follows:

```int sum=0,t;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
if(a[j].data==i)
sum++;
if(maxx<sum)
{
maxx=sum;
t=i;
}//maxx=maxx>sum? Maxx: sum should be OK, too. The author hasn't tried (from if (Maxx < sum) to here. Replace it with Maxx = Maxx > sum? maxx:sum))
sum=0;
}
cout<<t<<endl;```

Basically, the difficulty is here. Next, output all the child nodes of t

Next, from small to large, no weight and no leakage, a [i] Data = 0:

The code snippet is as follows (f at this time, this is to determine whether to enter spaces):

```for(int i=0;i<n;i++)
{
if(a[i].data==t)
{
if(f)
cout<<" ";
cout<<i;
f++;
}
}```

Full code:

```#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
}a[101];
int main()
{
int n,m,x,y,root,maxx=-1;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>x>>y;
a[y].data=x;
}
for(int i=0;i<n;i++)
{
if(a[i].data==0)
{
root=i;
break;
}
}
cout<<root<<endl;
int f=0,t;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
if(a[j].data==i)
f++;
if(maxx<f)
{
maxx=f;
t=i;
}
f=0;
}

cout<<t<<endl;
f=0;
for(int i=0;i<n;i++)
{
if(a[i].data==t)
{
if(f)
cout<<" ";
cout<<i;
f++;
}
}
return 0;
}```

If you came here to copy the code, sorry, the above is the error code. If you read my solution carefully, you may think: what about the third bug?

Here it comes:

## The third bug:

Cycle must start from 1!!!

(in order not to let those who copy the code directly point to it, I won't make the title)

AC Code:

```#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
}a[101];
int main()
{
int n,m,x,y,root,maxx=-1;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
a[y].data=x;
}
for(int i=1;i<=n;i++)
{
if(a[i].data==0)
{
root=i;
break;
}
}
cout<<root<<endl;
int f=0,t;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
if(a[j].data==i)
f++;
if(maxx<f)
{
maxx=f;
t=i;
}
f=0;
}

cout<<t<<endl;
f=0;
for(int i=1;i<=n;i++)
{
if(a[i].data==t)
{
if(f)
cout<<" ";
cout<<i;
f++;
}
}
return 0;
}```

It's not easy to make. Don't spray if you don't like it

Pay attention and find more wonderful content!!!

Keywords: C++ data structure

Added by BioBob on Wed, 09 Feb 2022 06:38:02 +0200