M

题目连接 http://acm.hust.edu.cn/vjudge/contest/121192#problem/M

题目要求输出可能的先后顺序，前后问题可以用拓扑排序（递归和DFS），根据题意使用队列，栈等。拓扑排序由两个函数

实现（topo，dfs).

#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;

const int MAX = 100+5;

int g[MAX][MAX], vis[MAX];
int n, m;
stack<int> s;

bool dfs(int u)
{
    vis[u]=-1;
    for(int v=1; v <= n; v++)
    {
        if(g[u][v])
        {
            if(vis[v]<0) return false; // 在栈中即表示有环
            else if(!vis[v] && !dfs(v)) return false;  //满足条件的是 V 没有被访问过 vis(v)=0 dfs(v)=0
        }
    }
    vis[u]=1;
    s.push(u);
    return true;
}

bool topoSort()
{
    int count=0;
    for(int i=1; i <= n; i++)
    {
        if(!vis[i])  //如果没有访问过的点
        {
            if(!dfs(i))  //dfs=0
                return false;
        }
    }
    return true;
}

void init()
{
    while(!s.empty())
        s.pop();
    memset(g, 0, sizeof(g));
    memset(vis, 0, sizeof(vis));
}

int main()
{
    while(cin>>n>>m)
    {
        if(m==0 && n==0)
            break;

        init();
        int u, v;
        for(int i=0; i < m; i++)
        {
            cin>>u>>v;
            g[u][v]=1;
        }
        if(topoSort())
        {
            while(!s.empty())
            {
                cout << s.top() << " ";
                s.pop();
            }
            cout << endl;
        }
    }
    return 0;
}