反復トポロジソート

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;
}