UVa 10305 - Ordering Tasks【拓扑排序】

Ordering Tasks

#include<cstdio>
#include<algorithm>
#include<cstring>
const int maxn=110;
int c[maxn],topo[maxn],t,n,G[maxn][maxn];
bool dfs(int u){
    c[u]=-1;
    for(int v=1;v<=n;v++)
        if(G[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 i=1;i<=n;i++)
        if(!c[i]&&!dfs(i))  return false;
    return true;
}
int main()
{
    int m;
    while(scanf("%d%d",&n,&m),n||m){
        int u,v;
        memset(G,0,sizeof(G));
        for(int i=0;i<m;i++){
            scanf("%d%d",&u,&v);
            G[u][v]=1;
        }
        if(toposort())
            for(int i=0;i<n;i++){
                if(i!=0) printf(" ");
                printf("%d",topo[i]);
            }
        printf("\n");
    }
    return 0;
}

UVa 10305 - Ordering Tasks【拓扑排序】

原文：http://blog.csdn.net/a995549572/article/details/46538973