轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年5月24日 星期六

TOJ::165 / 陣線推進

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




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

#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;
}

沒有留言:

張貼留言