拓扑排序的应用

一、判断有向图有无回路或者自环，如果当某一个点在，完成到该点的拓扑排序后，他的入度仍旧不等于0，说明这个点存在自环或者在回路内部。

拓扑排序遇到回路或自环后会无法往下面进行，所以所有与自环或回路有联系的点都无法被遍历。

例题： G. How Many Paths?

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int M=4e5+5;
vector<int> c[M];
int ind[M];
int vis[M];
int ans[M];
void dfs1(int u){
	vis[u]=1; ans[u]=1;
	for(int i=0;i<c[u].size();i++){
		int p=c[u][i];
		if(vis[p]){
			ans[p]=2;
			continue;
		}
		dfs1(p);
	}
}

void dfs2(int u,int now){
	vis[u]=1;
	if(ans[u]==2) now=2;
	ans[u]=now;
	for(int i=0;i<c[u].size();i++){
		int p=c[u][i];
		if(vis[p]) continue;
		dfs2(p,now);
	}
}

void topo(){
	if(ans[1]==2){
		for(int i=1;i<=n;i++){
			if(ans[i]) ans[i]=-1;
		}
		return;
	}
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int u=q.front(); q.pop();
		vis[u]=1;
		for(int i=0;i<c[u].size();i++){
			int p=c[u][i];
			ind[p]--;
			if(!ind[p]) q.push(p);
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]&&ans[i]) ans[i]=-1;
	}
}

int main(){
	int t; cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			c[i].clear();
			ind[i]=0;
			vis[i]=0;
			ans[i]=0;
		}
		for(int i=1;i<=m;i++){
			int u,v; cin>>u>>v;
			c[u].push_back(v);
			ind[v]++;
		}
		dfs1(1);
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				for(int j=0;j<c[i].size();j++){
					int p=c[i][j];
					ind[p]--;
				}
			}
		}
		for(int i=1;i<=n;i++) vis[i]=0;
		dfs2(1,1);
		for(int i=1;i<=n;i++){
			vis[i]=0;
		}
		topo();
		for(int i=1;i<=n;i++){
			cout<<ans[i]<<" ";
		}
		cout<<endl;
	}
  return 0;
}

持续更新ing~