在图论中，拓扑排序是有向无环图（DAG) 所有顶点的线性序列
若存在一条从顶点A 到顶点B 的路径，那么在序列中顶点A出现在 顶点B的前面
此图全部顶点被输出：说明说明图中无「环」存在， 是 AOV 网
没有输出全部顶点：说明图中有「环」存在，不是 AOV 网
必需概念 ： 入度 -- 顶点x作为例如A - B中 B 的终点次数
出度 -- 顶点x作为发出边点的次数
做法 ： 1.找到入度为零的点，加入队列，作为起点
2.从起点遍历所有边，每个终点的入度-1，直到有新的点入度为0，再将其加入队列
3.重复操作2，直到队列为空
【模板】拓扑排序 / 家谱树
题目描述
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。
输入格式
第 \(1\) 行一个整数 \(N\)（\(1 \le N \le 100\)），表示家族的人数。接下来 \(N\) 行，第 \(i\) 行描述第 \(i\) 个人的后代编号 \(a_{i,j}\)，表示 \(a_{i,j}\) 是 \(i\) 的后代。每行最后是 \(0\) 表示描述完毕。
输出格式
输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。
样例 #1
样例输入 #1
5
0
4 5 1 0
1 0
5 3 0
3 0
样例输出 #1
2 4 5 3 1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100101;
struct node{
int from;
int to;
int next;
}e[N];
int head[N],cnt;
void add(int u,int v)
{
++cnt;
e[cnt].from = u;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
int n,m;
int du[N];
queue<int> q;
vector<int> v;
int main()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>m;
while(m)
{
add(m,i);
du[i]++;
cin>>m;
}
}
for(int i = 1; i <= n; i++)
if(du[i] == 0)
q.push(i);
while(!q.empty())
{
int x = q.front();
v.push_back(x);
q.pop();
for(int i = head[x];i;i = e[i].next)
{
int y = e[i].to;
du[y]--;
if(du[y] == 0)
q.push(y);
}
}
for(int i = v.size() - 1; i >= 0; i --)
{
cout<<v[i]<<" ";
}
return 0;
}