在图论中，拓扑排序是有向无环图（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

样例输出 #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;
 }