トポロジをソートし、可能なシーケンスを出力

1223 ワード

問題の説明のように、与えられた図に基づいて可能なトポロジーシーケンスを出力する.トポロジーソートが可能かどうかを判断する鍵は、図にループがあるかどうかだ.
ここでは,配列cの値で頂点の現在の状態を表す.0は訪問されていないことを表し、-1は訪問されていることを表し、1はその点とその子孫が訪問されたことを表し、存在しないループの点である.では,dfsを用いて遍歴し,この点がアクセス中に再びアクセスされると,ループが存在することを実証した.あるいは、このポイントはアクセスされていませんが、後続の要素に再帰的にアクセスするときにループが存在し、リターンに失敗します.
コードを見てください:
#include
#include
#include
#include
#include
#define INF 100000000;
using namespace std;
const int maxn = 10000 + 5;
int mp[maxn][maxn];
int c[maxn],topo[maxn],t,n;
bool dfs(int u) {
	c[u] = -1;//        
	for(int v = 0; v < n; v++) {
		if(mp[u][v])
			if(c[v] < 0) return false;//       ,      ,     
			else if(!c[v]&&!dfs(v)) return false;//         
	}
	c[u] = 1;//           ,      
	topo[--t] = u;//      ,    ,       
	return true;
}
bool toposort() {
	t = n;
	memset(c,0,sizeof(c));
	for(int u = 0; u < n; u++)
		if(!c[u])
			if(!dfs(u))
				return false;
	return true;
}

int main() {
	int e,x,y,t;
	cin>>e>>n;
	for(int i = 0; i < e; i++) {//   
		cin>>x>>y;
	   	mp[x][y] = 1;
	}
	cout<