PAT 甲级 1146 Topological Order (25 分)

思路：

1.一个简单的求拓扑排序(Topological Order)的算法是找出任意一个入度为0的顶点，然后删去该顶点，然后对图的剩余部分做相同的操作，删去的顶点序列即是一个拓扑序列；
2.根据题目所给的有向边，用数组存储每个顶点的入度，用vector数组存储每个顶点下一个可达顶点（有多个可达顶点）；
3.根据需要查询的序列，从前往后，每个顶点的入度都要为0，每试一个顶点且此顶点符合要求，此顶点的下一个可达顶点的入度都减一；若有一个不符合则输出该轮次序号；

代码：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n,m,k;
	scanf("%d%d",&n,&m);
	vector<int> v[1001],notTopo,vin(n+1);
	for(int i=0;i<m;i++)
	{
		int v1,v2;
		scanf("%d%d",&v1,&v2);
		vin[v2]++;
		v[v1].push_back(v2);
	}
	scanf("%d",&k);
	for(int i=0;i<k;i++)
	{
		int ver,sign=1;
		vector<int> vinn(vin);
		for(int j=0;j<n;j++)
		{
			scanf("%d",&ver);
			if(vinn[ver]&&sign)
			{
				notTopo.push_back(i);
				sign=0;
			}
			else if(!vinn[ver]&&sign)
				for(auto k:v[ver]) vinn[k]--;
		}
	}
	printf("%d",notTopo[0]);
	for(int i=1;i<notTopo.size();i++) printf(" %d",notTopo[i]);
	return 0;
}