拓扑排序

浏览数：23 / 时间：2015年06月08日

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
#define maxn 105
int n,m,t;
int a[maxn][maxn];
int vis[maxn],des[maxn];

bool dfs(int u)
{
    vis[u]=-1;
    for(int i=1; i<=n; i++)
        if(a[u][i])
    {
        if(vis[i]==-1) return false;
    else if(!vis[i]&&!dfs(i)) return false;
    }
    vis[u]=1;
    des[--t]=u;
    return true;
}



int main()
{
    while(~scanf("%d%d",&n,&m)&&n+m)
    {
        t=n;
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));

        int p,q;
        for(int i=0; i<m; i++)
        {
            cin>>p>>q;
            a[p][q]=1;
        }
        for(int i=1; i<=n; i++)
         if(!vis[i])
             dfs(i);
        for(int i=0; i<n; i++)
        {
            if(!i) cout<<des[i];
            else cout<<" "<<des[i];
        }
        cout<<endl;
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

拓扑排序