UVa10305 - Ordering Tasks(拓樸排序)

題目大意

John 有很多任務要做，但有些任務息息相關，希望你可以幫他寫出一份任務清單讓他來做任務

題目連結

重點觀念

• 拓樸排序的應用

分析

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

標準模板題，但要注意必需 n and m 都要是 0 才可以把程式終止喔，這題會有 n or m 一個零的情況。

參考連結

師大演算法 - Topological Ordering

心得

這題真的是師大演算法給我大助攻阿！發現開學後我的腦袋變得沒有原本寒假時候清晰了，太多雜事要忙要做了，都沒有辦法用心做這件事，以前還記得的演算法現在都忘記了，現在趕快補這些知識回來。

題目程式碼

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

下面 topo function 的程式碼 演算法知識 - Topological Ordering 拓樸排序(時間複雜度 O(V+E)) 相同，就不寫講解，如果不太懂直接看此網頁就好。

• 紀錄關係
  a,b ，則 a 必須在 b 前面、c,d，則 c 必須在 d 前面，此時我們會稱 a,c 為前面節點、b,d 是後面節點。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 120
using namespace std;
int n, m, a, b;
int cnt[MAXN]; 
vector<int> root[MAXN], ans;

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

    int now;
    ans.clear();
    while(ans.size() != n){
        if(q.empty()) break;
        now = q.front(); q.pop_front();
        ans.push_back(now);
        for(auto it: root[now]){
            cnt[it]--;
            if(cnt[it] == 0) q.push_back(it);
        }
    }
    if(ans.size() == n){
        cout << ans[0];
        for(int i = 1; i < ans.size(); i++) cout << ' ' << ans[i];
        cout << '\n';
    }
}

int main(){
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> n >> m && n + m != 0){
        for(int i = 1; i <= n; i++) root[i].clear(); //將資料清空，以免這次測資被上次測資干擾
        memset(cnt, 0, sizeof(cnt)); 
        for(int i = 0; i < m; i++){ //輸入資料
            cin >> a >> b;
            root[a].push_back(b); //記錄關係，記錄 a 有多少後面節點，並且記錄。
            //這裡的後面節點須看 [大衛的筆記 拓樸排序] 意思。
            cnt[b]++; //記錄有幾個前面節點
        }
        topo(); //拓樸排序開始
    }

}