(UVA) 11060 - Beverages

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2001

題目大意：給你n個東西及m個限制。要求輸出符合m個限制的排列。如果兩兩間沒有特別的限制(在m裡面的限制)，用輸入的順序判斷。

sol : 把寫topological 的 queue 改成 priority_queue 即可！！！

因為，用min heap的話，就變成可以維護相對關係了！

複雜度：O(n lg n)  //map + heap


#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
using namespace std;

const int MAX_N = 103;

string s[MAX_N];
int rudu[MAX_N];
map<string,int> mp;
vector<int> edg[MAX_N];

int main () {
//    freopen("output.txt","w",stdout);
    //好久沒用cin XD ;
    int n;
    int cases=1;
    while (scanf("%d",&n) != EOF) {
        mp.clear();
        for (int x=0;n>x;x++) {
            rudu[x]=0;
            edg[x].clear();
        }
        for (int x=0;n>x;x++) {
            cin >> s[x];
            mp[s[x]] = x;
        }
        int m;
        scanf("%d",&m);
        for (int x=0;m>x;x++) {
            string a,b;
            cin >> a >> b;
            rudu[mp[b]] ++;
            edg[mp[a]].push_back(mp[b]);
        }
        printf("Case #%d: Dilbert should drink beverages in this order:",cases++);
        priority_queue<int,vector<int> , greater<int> > que;
        for (int x=0;n>x;x++) {
            if (rudu[x] == 0) que.push(x);
        }
        while (!que.empty()) {
            int t=que.top();
            que.pop();
            cout<<' '<<s[t];
            for (vector<int>::iterator i=edg[t].begin();i!=edg[t].end();i++) {
                int tmp=*i;
                rudu[tmp]--;
                if (rudu[tmp] == 0) que.push(tmp);
            }
        }
        puts(".\n");
    }
}