拓扑排序

拓扑排序

#include <bits/stdc++.h>
using namespace std;
const int maxn=99999999;
vector<int>vec[maxn];
int indug[maxn],n;
void tuopu()
{
	queue<int>d;
	for(int i=1;i<=n;i++)	
		if(indug[i]==0)
			d.push(i);//添加入度为0的点
	while(!d.empty())
	{
		int temp=d.front();
		d.pop();
		for(int i=0;i<vec[temp].size();i++)//把所有和temp有关的边都删掉
			if(--indug[vec[temp][i]]==0)	d.push(vec[temp][i]);//碰到入度为0的再次入队	
	}
	//那么，最后剩下的就是环 
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)//读边
	{
		int l,r;
		cin>>l>>r;
		indug[r]++;
		vec[l].push_back(r);
	}
	tuopu(); 
}