[UVA] 10305 - Ordering Tasks

題意:
輸入節點數和有向邊的數量，
接下來輸入節點 A 指向節點 B ，
最後要輸出的是一拓樸排序，
當 A 指向 B ，就要先輸出 A 再輸出 B ，
範例輸入
5 4
1 2
2 3
1 3
1 5
只要滿足節點 1 在 2 3 5 之前輸出以及 2 在 3 之前輸出即可，
所以也可以輸出
4 1 5 2 3
--------------------------------------------------

方法:
拓樸排序，
先利用 DFS 到最深層的節點，
表示該節點一定可以先輸出，
那麼有指向其他節點的一定會比較後面輸出，
根節點也會最後輸出~
--------------------------------------------------

/* 20150827
 * hanting
 * UVa 10305 - Ordering Tasks
 * C++
 */
#include <iostream>
#include <vector>
#include <cstring>//memset
using namespace std;
vector<int> ans;
void Topology(vector<int> *vec,int *visit,int cur)
{
    static int flag=1;
    visit[cur]=flag++;
    for(int i=0;i<vec[cur].size();i++)
    {
        int t=vec[cur][i];
        if(!visit[t])
        {
            Topology(vec,visit,t);
        }
    }
    ans.push_back(cur);
}
int main()
{
    int N,messageN;
    while(cin>>N>>messageN and N+messageN)
    {
        ans.clear();
        vector<int> vec[N+1];
        for(int i=0;i<messageN;i++)
        {
            int a,b;
            cin>>a>>b;
            vec[a].push_back(b);
        }
        int visit[N+1];
        memset(visit,0,sizeof(visit));
        for(int i=1;i<N+1;i++)
        {
            if(!visit[i])
            {
                Topology(vec,visit,i);
            }
        }
        for(int i=ans.size()-1;i>0;i--)
        {
            cout<<ans[i]<<" ";
        }
        cout<<ans[0]<<endl;
    }
    return 0;
}