拓扑排序

拓扑排序是一个有向无环图的所有顶点的线性序列。

该序列需要满足每个顶点出现且只出现一次和如果有一条 AA 到 BB 的路径，在序列中 AA 出现在 BB 的前面。

queue <int> Q;
void toposort() {
	for(int i = 1; i <= n; i++) {
		printf("%d ", i);
		Q.push(i);
	}
	while(Q.size()) {
		int x = Q.front(); Q.pop();
		for(int i = Head[x]; i; i = Next[i]) {
			deg[to[i]]--;
			if(deg[to[i]] == 0) {
				printf("%d ", to[i]);
				Q.push(to[i]);
			}
		}
	}
}

拓扑排序的步骤：

计算每个点的入度。

入度为 00 就加入队列。

当队列不为空则循环：

取出队首元素并输出。

遍历队首元素的连边，对应节点的入度 -1−1。

当对应的节点入度为 00 就加入队列。