首页 > 代码库 > poj2367拓扑排序入门

poj2367拓扑排序入门

#include<stdio.h>#include<iostream>#include<string.h>#include<queue>#include<stack>#include<list>#include<stdlib.h>#include<algorithm>#include<vector>#include<map>#include<set>#include <fstream>using namespace std;const int Maxn=200;int c[Maxn],topo[Maxn],t;int n;int G[Maxn][Maxn];bool dfs(int u){    c[u]=-1;    for(int v=n;v>=1;v--) {        if(G[u][v]){           // printf("%d %d", u, v);system("pause");            if(c[v]==-1) 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=1;u<=n;u++){        if(!c[u]) if(!dfs(u)) return false;    }    return true;}int main(){    while(cin>>n){        int cc;        memset(G,0,sizeof(G));        for(int i=1;i<=n;i++){            while(cin>>cc,cc){                G[i][cc]=1;;            }        }        bool flag;        flag = toposort();      //  printf("%d ",flag);system("pause");        if(flag) {            cout<<topo[0];            for(int i=1;i<n;i++)                printf(" %d",topo[i]);            cout<<endl;        }    }    return 0;}