【题目来源】
https://www.luogu.com.cn/problem/B3644

【题目描述】
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。

【输入格式】
第 1 行一个整数 N（1≤N≤100），表示家族的人数。接下来 N 行，第 i 行描述第 i 个人的所有后代编号。每行最后是 0 表示描述完毕。

【输出格式】
输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。

【输入样例】
5
0
4 5 1 0
1 0
5 3 0
3 0

【输出样例】
2 4 5 3 1

【算法分析】
● 拓扑排序算法概念
拓扑排序‌是针对‌有向无环图（DAG, Directed Acyclic Graph）‌的一种线性排序算法，使得对于图中的每一条有向边 (u, v)，u 在排序中总是位于 v 的前面。
有向图的拓扑序列详见：https://blog.csdn.net/hnjzsyjyj/article/details/116307687

● 拓扑排序算法步骤
（1）从有向图中选择一个无前驱（即入度为0）的顶点并且输出它。
（2）从图中删除该顶点及所有以它为尾的有向边。
（3）重复上述两步，直至不存在无前驱的顶点。
（4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列就是一个拓扑序列。

● “链式前向星”核心操作：https://blog.csdn.net/hnjzsyjyj/article/details/139369904
“链式前向星”就是“多单链表”，每条单链表基于“头插法”并用 e[]、ne[]、h[] 、val[] 等数组进行模拟创建。其中：
e[idx]：存储序号为 idx 的边的终点值
ne[idx]：存储序号为 idx 的边指向的边的序号（模拟链表指针）‌
h[a]：存储头结点 a 指向的边的序号
val[idx]：存储序号为 idx 的边的权值（可选）

【算法代码：链式前向星】

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e3+5;
int ind[maxn]; //inDegree
int h[maxn],e[maxn<<1],ne[maxn<<1],idx;
int n,x;

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void topsort() {
    queue<int> q;
    for(int i=1; i<=n; i++) {
        if(ind[i]==0) q.push(i);
    }

    while(!q.empty()) {
        int t=q.front();
        q.pop();
        cout<<t<<" ";
        for(int i=h[t]; i!=-1; i=ne[i]) {
            int j=e[i];
            ind[j]--;
            if(ind[j]==0) q.push(j);
        }
    }
}

int main() {
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1; i<=n; i++) {
        while(cin>>x && x) {
            add(i,x);
            ind[x]++;
        }
    }
    topsort();

    return 0;
}

/*
in:
5
0
4 5 1 0
1 0
5 3 0
3 0

out:
2 4 5 3 1
*/

【算法代码：邻接表】

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e3+5;
int ind[maxn]; //inDegree
vector<int> g[maxn];
int n,x;

void topsort() {
    queue<int> q;
    for(int i=1; i<=n; i++) {
        if(ind[i]==0) q.push(i);
    }

    while(!q.empty()) {
        int t=q.front();
        q.pop();
        cout<<t<<" ";
        for(int i=0; i<g[t].size(); i++) {
            int j=g[t][i];
            ind[j]--;
            if(ind[j]==0) q.push(j);
        }
    }
}

int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        while(cin>>x && x) {
            g[i].push_back(x);
            ind[x]++;
        }
    }
    topsort();

    return 0;
}

/*
in:
5
0
4 5 1 0
1 0
5 3 0
3 0

out:
2 4 5 3 1
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/116307687
https://www.cnblogs.com/jyssh/p/18829420
https://www.luogu.com.cn/problem/solution/B3644
https://www.acwing.com/problem/content/3707/
https://www.lanqiao.cn/problems/108/learning/