家谱树题解

(ACM比赛时忘了拓扑怎么写时代尻古)

假设有一个 DAG 图，那么如何写出它的拓扑排序呢？这里说一种比较常用的方法：

1.从 DAG 图中选择一个没有前驱（即入度为0）的顶点并输出。

2.从图中删除该顶点和所有以它为起点的有向边。
3.重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

#include<bits/stdc++.h>
using namespace std;
int n,mapp[1145][1145],in[114514],t;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		while(cin>>t&&t){
			mapp[i][t]=1;
			in[t]++;
		}
	}
	priority_queue<int,vector<int>,greater<int> > q;
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int now=q.top();
		q.pop();
		cout<<now<<" "; 
		for(int i=1;i<=n;i++){
			if(mapp[now][i]){
				in[i]--;
				mapp[now][i]=0;
				if(in[i]==0){
					q.push(i);
				}
			}
		}
	}
	return 0;
}