Informatics Olympiad 1336: [example 3-1] find roots and children

【 Topic link 】

ybt 1336：【 example 3-1】 Find roots and children

【 Topic test site 】

1. Trees Parenting

set up pa Array ,pa[i] It means the first one i The number of the parent node of the node .

【 Their thinking 】

solution 1： Parenting

Save the information of the whole tree with parental representation ,pa[i] It means the first one i The number of the parent node of the node . Traverse pa Array to find the degree of each node （ The degree of a node in a tree is the number of children in that node ）, Get the number of the node with the largest degree . Then traverse pa Array , Output the children of this node .

【 Solution code 】

solution 1： Parenting

#include <bits/stdc++.h>
using namespace std;
int par[101], deg[101];//par[i]: Represents a node i My parents , deg[i]: Represents a node i Degree 
int main()
{
    
    int n, m, x, y, root, maxDeg = 0, maxNum = 1;//root: Indicates the root node number ,maxNum: The node number with the highest degree ,maxDeg： Represents the degree of the node with the highest degree , That is, the number of children at the node with many children 
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
    
        cin >> x >> y;
        par[y] = x;//y My parents are x 
    }
    for(int i = 1; i <= n; ++i)
    {
    
        if(par[i] == 0)// Parents are 0 The node of is the root node  
            root = i;
        deg[par[i]]++;// node i Duega of parents 1
    }
    cout << root << endl;
    for(int i = 1; i <= n; ++i)// Find the node with the greatest degree 
    {
    
        if(deg[i] > maxDeg)
        {
    
            maxDeg = deg[i];// Maximum degree  
            maxNum = i;// The number of the vertex with the largest degree  
        }
    }
    cout << maxNum << endl;
    for(int i = 1; i <= n; ++i)// Traverse each node in sequence , See which nodes are the children of the largest nodes 
    {
    
        if(par[i] == maxNum)
            cout << i << ' ';
    }
    return 0;
}