<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。

给出每个人的孩子的信息。

输出一个序列，使得每个人的孩子都比那个人后列出。

输入格式

第 $1$ 行一个整数 $n$，表示家族的人数；

接下来 $n$ 行，第 $i$ 行描述第 $i$ 个人的孩子；

每行最后是 $0$ 表示描述完毕。

每个人的编号从 $1$ 到 $n$。

输出格式

输出一个序列，使得每个人的孩子都比那个人后列出；

数据保证一定有解，如果有多解输出任意一解。

数据范围

$1 \\le n \\le 100$

输入样例：

5
0
4 5 1 0
1 0
5 3 0
3 0

输出样例：

2 4 5 3 1

思路

看完这题，这不就是拓扑排序的模板题吗？啪的一下敲好——$AC$！

思想：不断选择入度为$0$的点$x$，把$x$连向的点的入度$-1$。
可以结合 bfs 的框架来高效实现这个过程：

1. 建立空的拓扑序列$A$.
2. 预处理所有点的入度$deg[i]$, 起初把所有入度为$0$的点入队。
3. 取出队头节点$x$, 把$x$加入拓扑序列$A$的末尾。
4. 对于从$x$出发的每条边$\lt x, y\gt$, 把$deg[y]- - $。若被减为$ 0$， 则把$ y $入队。
5. 重复第$ 3 \sim 4 $步直到队列为空， 此时$ A　$即为所求。

拓扑排序可以判断有向图是否存在环。我们可以对任意有向图执行上述过程，在完成后检查$A$序列的长度。 若$ A$序列的长度小于图中点的数量，则说明某些节点未被遍历，进而说明图中存在环。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110,M = N * N;
int n;
int h[N],e[M],ne[M],idx;
int in_deg[N];
int q[N],hh,tt;
void add (int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void top_sort () {
    tt = -1;
    for (int i = 1;i <= n;i++) {
        if (!in_deg[i]) q[++tt] = i;
    }
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t];~i;i = ne[i]) {
            int j = e[i];
            in_deg[j]--;
            if (!in_deg[j]) q[++tt] = j;
        }
    }
}
int main () {
    memset (h,-1,sizeof (h));
    cin >> n;
    for (int i = 1;i <= n;i++) {
        int x;
        while (cin >> x,x) {
            add (i,x);
            in_deg[x]++;
        }
    }
    top_sort ();
    for (int i = 0;i < n;i++) cout << q[i] << ' ';
    return 0;
}