【テンプレート】トポロジーソート

Kahnアルゴリズム

#include
#include
#include
#include
#include
using namespace std;
const int maxn=10000+5;
int n,m,tot,head[maxn],rd[maxn],a[maxn];
struct Edge{
	int next,to;
}e[maxn];
void Add(int x,int y){
	e[++tot].next=head[x];
	e[tot].to=y;
	head[x]=tot;
} 
void Kahn(){
	stack sta;
	for(int i=1;i<=n;i++){
		if(!rd[i])sta.push(i);
	}
	int cnt=0;
	while(!sta.empty()){
		int u=sta.top();sta.pop();a[++cnt]=u;
		for(int x=head[u];x;x=e[x].next){
			int v=e[x].to;
			rd[v]--;
			if(!rd[v])sta.push(v);
		}
	}
	if(cnt>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		Add(x,y);rd[y]++;
	}
	Kahn();
}

DFSトポロジ

#include
#include
#include
#include
#include
using namespace std;
const int maxn=10000+5;
int n,m,tot,cycle,vis[maxn],head[maxn],rd[maxn],a[maxn];
stack sta;
struct Edge{
	int next,to;
}e[maxn];
void Add(int x,int y){
	e[++tot].next=head[x];
	e[tot].to=y;
	head[x]=tot;
} 
void dfs(int u){
	if(cycle==1)return;
	vis[u]=-1;
	for(int x=head[u];x;x=e[x].next){
		int v=e[x].to;
		if(!vis[v])dfs(v);
		else if(vis[v]==-1){
			cout<>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		Add(x,y);rd[y]++;
	}
	for(int i=1;i<=n;i++){
		if(!rd[i])dfs(i);
	}
	if(cycle==0){
		while(!sta.empty())cout<

DP+トポロジ

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e4+5;
int n,m,len,cnt,tot,head[maxn],rd[maxn],f[maxn];
struct Edge{
	int next,to,w;
}e[maxn];
void Kahn(){
	stack sta;
	for(int i=0;i>x>>y>>z;
			Add(x,y,z);rd[y]++;
		}
	}
	Kahn();
}