Code 備忘錄►Graph

TOJ::165 / 陣線推進

http://2014.sprout.csie.org/oj/pro/165/
拓撲排序

這題是拓樸排序，但是要注意題目要求依照字典序最小輸出。
其實只要將原本的queue，換成priority_queue就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define N 100001
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
int D[N],ST[N],st;
int main(int argc,char *argv[])
{
    ios_base::sync_with_stdio(false);
    int n,m,a,b;
    cin>>n;
    while(cin>>n>>m){
        memset(D,0,sizeof(D));
        st=0;
        vector<int> M[N];
        F(m){
            cin>>a>>b;
            M[a].push_back(b);
            D[b]++;
        }
        priority_queue<int>qq;
        F(n)if(D[i]==0)qq.push(-i);
        while(!qq.empty()){
            int now=-qq.top();
            qq.pop();
            ST[st++]=now;
            F(M[now].size())
                if(--D[M[now][i]]==0)qq.push(-M[now][i]);
        }
        if(st==n){
            cout<<ST[0];
            F(n-1)cout<<' '<<ST[i+1];
        }
        else cout<<"QAQ";
        cout<<endl;
    }
    return 0;
}