反復トポロジソート
10042 ワード
this topologically sortは優先キューを使って同級のノードを並べ替えた
#include
#include
using namespace std;
int n,m,topo[100]; //topo
int G[100][100]; //
int c[100]; //
int t;
bool dfs(int u){
c[u]=-1;
// , u
for(int v=1;v<=n;v++) { //
if(G[u][v]) // dfs
{
if(c[v]==-1) // ,
return false;
if(c[v]==0){
if(!dfs(v)) //
return false;
}
}
}
c[u]=1; //
topo[--t]=u; //
return true;
}
int main(){
int a,b;
cin>>n>>m;
t=n;
memset(G,0,sizeof(G));
memset(c,0,sizeof(c));
for(int i=0;i<m;i++) {
cin>>a>>b;
G[a][b]=1;
}
for(int u=1;u<=n;u++) {
if(!c[u]) //
if(!dfs(u)){ //dfs ,
cout<<" , "<<endl;
return 0;
}
}
for(int i=0;i<n;i++)
cout<<topo[i]<<" "<<endl;
return 0;
}