UVa11060 - Beverages(拓樸排序)

題目大意

Dilbert 是一位學生，他喜歡喝酒的時候先喝低濃度酒精飲料，之後慢慢變濃，不會再回去喝比較低的酒精飲料，給你他要喝的飲料，在給你一些酒精的先後關係，請給他一種飲料排序是可以符合他的喝酒規則。

題目連結

重點觀念

• 拓樸排序的應用
• 將酒精飲料 hash 成數值

分析

簡單的拓樸排序，如果不太懂拓樸排序就看 演算法知識 - Topological Ordering 拓樸排序(時間複雜度 O(V+E))，有對於一些拓樸排序有些基礎的教學，希望大家都可以看懂。

心得

最近不斷在複習演算法，但是內心卻因為感情的事情不斷在擔憂，真的好煩。

好希望自己能夠安靜下心來，順利做完每個任務，好想讓自己可以變成一個溫暖、開心的人。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

關於 function topo 的程式碼說明請大家點拓樸排序，有更完整的解釋，會讓讀者更好吸收。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 220
using namespace std;
int cnt[MAXN];
vector<int> root[MAXN];
map<string, int> mp; //飲料 hash 成數字
map<int, string> mp2; //還原 hash
int n, m, kase; //題目資訊

void topo(){
    deque<int> q;
    for(int i = 0; i < n; i++){
        if(cnt[i] == 0) q.push_back(i);
    }

    deque<int> ans;
    int now;
    while(ans.size() != n){
        if(q.empty()) break;
        sort(q.begin(), q.end());
        now = q.front(); q.pop_front();
        ans.push_back(now);
        for(auto it: root[now]){
            if(--cnt[it] == 0) q.push_back(it);
        }
    }

    if(n == ans.size()){ //輸出資料
        cout << "Case #" << ++kase << ": Dilbert should drink beverages in this order:";
        for(auto it: ans) cout << ' ' << mp2[it];
        cout << ".\n\n";
    }

}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    string temp, temp2; //輸入題目資料
    while(cin >> n){
        for(int i = 0; i < n; i++){ //輸入資料
            root[i].clear(); //先清空之前資料 
            cnt[i] = 0; //清除之前的記錄關係
            cin >> temp;
            mp[temp] = i; //hash，由於 i 值相對應每一個資料，不會碰撞所以就用 i hash
            mp2[i] = temp; //記錄還原
        }
        cin >> m; //輸入記錄關係
        for(int i = 0; i < m; i++){ //不斷輸入 
            cin >> temp >> temp2;
            root[mp[temp]].push_back(mp[temp2]); 
            //記錄關係，記錄 a 有多少後面節點，並且記錄。
            cnt[mp[temp2]]++; //記錄有幾個前面節點，如果 b 是後面關係時。
        }
        topo();
    }

    return 0;
}