L2-026 small generation (25 points)

The title of this brush is 2021 Nian TIANTI

L2-026 Junior (25 branch )

This topic gives the genealogy of a large family , Please give a list of the youngest generation .

Input format ：

Enter in the first line to give the total family population N（ No more than 100 000 The positive integer ） —— Simplicity , We take family members from 1 To N Number . Then the second line gives N Number , Among them the first i The number corresponds to the i Father of member / mother . The father of the oldest ancestor in the family tree / The parent number is -1. The numbers in a row are separated by spaces .

Output format ：

First of all, output the smallest generation （ The ancestors are divided into 1, The following is increasing step by step ）. Then in the second line, output the number of the member with the lowest rank in ascending order . Numbers are separated by a space , There must be no extra space at the beginning and end of the line .

sample input ：

9
2 6 5 5 -1 5 6 4 7

sample output ：

4
1 9

Answer key

It's easier to see ：

x It's the father i It's the son

need x Add son , The reason is possible x There are many sons

And then use bfs perhaps dfs Just ask

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int n = 100005;
int N;
vector<int> v[n];
// BFS seek 
void bfs(int root)
{
    //  The first is serial number 
    //  The minor bit is algebra 
    queue<pair<int, int>> q;
    q.push({root, 0});
    //  The final answer 
    vector<int> ans;
    //  Algebra. 
    int maxt = 0;
    while (!q.empty())
    {
        auto x = q.front();
        q.pop();
        //  If a higher generation is found 
        //  Update 
        if (maxt < x.second)
        {
            maxt = x.second;
            ans.clear();
        }
        ans.push_back(x.first);
        for (auto &e : v[x.first])
            q.push({e, x.second + 1});
    }
    cout << maxt + 1 << endl;
    int f = 0;
    for (auto &e : ans)
    {
        if (f++ != 0)
            cout << " ";
        cout << e;
    }
}
int main()
{
    cin >> N;
    int root = 0;
    int x;
    for (int i = 1; i <= N; i++)
    {
        cin >> x;
        if (x == -1)
        {
            root = i;
            continue;
        }
        v[x].push_back(i);
    }
    bfs(root);
    return 0;
}