Given a family tree, the task is to output the smallest generation (youngest descendants) and list all members belonging to that generation.

Input Format: The first line contains an integer N (1 ≤ N ≤ 100,000), the total number of family members, each assigned a unique ID from 1 to N. The second line provides N integers where the i-th integer represents the parent ID of member i. The root ancestor (highest generation) has a parent ID of -1. Numbers are separated by spaces.

Output Format: Print the smallest generation number on the first line (the root is generation 1). On the second line, output the IDs of all members with that genertaion in increasing order, separated by spaces, with no extra spaces at the start or end.

Example Input:

9
2 6 5 5 -1 5 6 4 7

Example Output:

4
1 9

Depth-First Search Implementation

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_NODES = 200010;
vector<int> children[MAX_NODES];
int generation[MAX_NODES];
int rootId;

void computeGenerations(int currentNode, int parentGen) {
    generation[currentNode] = parentGen + 1;
    for (int child : children[currentNode]) {
        computeGenerations(child, generation[currentNode]);
    }
}

int main() {
    int memberCount;
    cin >> memberCount;
    
    for (int i = 1; i <= memberCount; i++) {
        int parentId;
        cin >> parentId;
        if (parentId == -1) {
            rootId = i;
        } else {
            children[parentId].push_back(i);
        }
    }
    
    computeGenerations(rootId, 0);
    
    int maxGen = 0;
    for (int i = 1; i <= memberCount; i++) {
        maxGen = max(maxGen, generation[i]);
    }
    
    vector<int> youngestMembers;
    for (int i = 1; i <= memberCount; i++) {
        if (generation[i] == maxGen) {
            youngestMembers.push_back(i);
        }
    }
    
    sort(youngestMembers.begin(), youngestMembers.end());
    
    cout << maxGen << endl;
    for (size_t i = 0; i < youngestMembers.size(); i++) {
        if (i > 0) cout << " ";
        cout << youngestMembers[i];
    }
    cout << endl;
    
    return 0;
}

Breadth-First Search Implementtaion

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

const int MAX_NODES = 200010;
vector<int> descendants[MAX_NODES];
int genLevel[MAX_NODES];
int rootId;

void determineGenerations() {
    queue<int> nodeQueue;
    fill(genLevel, genLevel + MAX_NODES, INT_MAX);
    
    genLevel[rootId] = 1;
    nodeQueue.push(rootId);
    
    while (!nodeQueue.empty()) {
        int current = nodeQueue.front();
        nodeQueue.pop();
        
        for (int nextNode : descendants[current]) {
            if (genLevel[nextNode] > genLevel[current] + 1) {
                genLevel[nextNode] = genLevel[current] + 1;
                nodeQueue.push(nextNode);
            }
        }
    }
}

int main() {
    int totalMembers;
    cin >> totalMembers;
    
    for (int i = 1; i <= totalMembers; i++) {
        int parent;
        cin >> parent;
        if (parent == -1) {
            rootId = i;
        } else {
            descendants[parent].push_back(i);
        }
    }
    
    determineGenerations();
    
    int youngestGen = 0;
    for (int i = 1; i <= totalMembers; i++) {
        youngestGen = max(youngestGen, genLevel[i]);
    }
    
    vector<int> youngestIds;
    for (int i = 1; i <= totalMembers; i++) {
        if (genLevel[i] == youngestGen) {
            youngestIds.push_back(i);
        }
    }
    
    sort(youngestIds.begin(), youngestIds.end());
    
    cout << youngestGen << endl;
    for (size_t i = 0; i < youngestIds.size(); i++) {
        if (i > 0) cout << " ";
        cout << youngestIds[i];
    }
    cout << endl;
    
    return 0;
}