拓补排序

1. 理解难度

   我觉得挺好理解的。

2. 用途

   求有向无环图的拓补序列。

3. 具体操作

   • 将入度为$0$的全部进队，放到答案序列里
   • 队列不空？
   • 取队头元素遍历，遍历到的点入度$-1$
   • 如果这些点现在入度是$0$了就进队，放到答案序列里

4. 代码

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=200001,inf=0x3f3f3f3f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
int n,r[N],m,head[N],totm;
int tot,ans[N];
queue<int> q;
struct bian{
	int next,to,w;
	bian(){
        w=0;
		next=0;
	}
}e[N];
void add(int s,int ed,int rm=0){
	e[++totm].next=head[s];
	e[totm].to=ed;
    e[totm].w=rm;
	head[s]=totm;
}
int main(){
	n=read(),m=read();
	fs(i,1,m,1){
		int u=read(),v=read();
		add(u,v);
		r[v]++;
	}
	fs(i,1,n,1){
		if(!r[i]){
			q.push(i);
			ans[++tot]=i;
		}
	}
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=head[now];i;i=e[i].next){
			int v=e[i].to;
			r[v]--;
			if(!r[v]){
				q.push(v);
				ans[++tot]=v;
			}
		}
	}
	if(tot<n){
		puts("-1");//有环 
		return 0;
	}
	fs(i,1,n,1) printf("%d ",ans[i]);
	return 0;
}