トポロジをソートし、可能なシーケンスを出力
1223 ワード
問題の説明のように、与えられた図に基づいて可能なトポロジーシーケンスを出力する.トポロジーソートが可能かどうかを判断する鍵は、図にループがあるかどうかだ.
ここでは,配列cの値で頂点の現在の状態を表す.0は訪問されていないことを表し、-1は訪問されていることを表し、1はその点とその子孫が訪問されたことを表し、存在しないループの点である.では,dfsを用いて遍歴し,この点がアクセス中に再びアクセスされると,ループが存在することを実証した.あるいは、このポイントはアクセスされていませんが、後続の要素に再帰的にアクセスするときにループが存在し、リターンに失敗します.
コードを見てください:
ここでは,配列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<