UVa872 - Ordering(拓樸排序)

題目大意

有一種排序是，給你一些英文字母，再告訴你某個英文字母必須要在另個英文字母前面(定義為記錄關係)。

請輸出一種排序可以符合題目的所有記錄關係。

題目連結

重點觀念

• 拓樸排序的應用
• 如何輸入

分析

這邊我用另種方式來寫拓樸排序，想說透過 DFS 的方式看能否寫出拓樸排序，但我認為我寫得不太好，這是我的自創方式，建議還是不要多看這個。

但如果想要了解我的思考，還是建議看看。

這題比較不好輸入，要用上 stringstream 這是類似於 cin，透過這個可以方便輸入題目資料，再來記錄所有的記錄關係，每次進行 DFS 時，確認之前的 DFS 的資料都有符合記錄關係才繼續，如果沒有就退回上層 DFS。

缺點是每層 DFS 都要做一次確認，時間複雜度會爆炸多，建議在比賽中還是不要使用。

DFS 只要能夠成功就一定會是拓樸排序，因為每層都會確認關係，因此只要走到 DFS 深度與原本序列一樣長就可以。

參考連結

UVa872 - morris821028

心得

其實我一開始已經忘記拓樸排序了，那是高中學的，上了大學後都忘記了…，然後在根據 Competitive Programming3，複習的過程中在寫這題 UVA，翻著有沒有其他人寫詳解，結果發現 morris821028 沒有寫詳解QQ，但是有 github，就看著他的程式碼來解，但後來發現師大演算法的 BFS 版本更好，後面就改用師大演算法的了。

很感謝師大演算法與 morris821028 大大，願意讓學習資源在網路上才有辦法讓我學習到，很感謝他們。

題目程式碼

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 40
using namespace std;
stringstream ss;
int graph[MAXN], visit[MAXN]; //graph 由於題目給的是字串，所以我們把它 hash 成 int
//visit 判斷這個點有沒有被 DFS 經歷過
int order[MAXN][MAXN]; //order 記錄關係
int n, lg, flag2, flag3; //n 測資長度, lg 每一個陣列長度
//flag2 判斷有沒有辦法拓樸排序, flag3 控制每個測資的斷行
char ch; //用來讀字元
vector<int> ans; //記錄拓樸排序的陣列

void dfs(int x){
    visit[x] = 1; //這個點被經歷過
    ans.push_back(x); //放入 ans

    //for(auto it: ans) cout << (char) (it + 'A') << ' ';
    //cout << '\n';

    if(ans.size() == lg){ //如果答案陣列跟原本陣列長度一樣
        flag2 = 0; //有找到拓圖排序
        cout << (char) (ans[0] + 'A'); //輸出第一個字元，這裡是嚴格輸出
        //輸出資料
        for(int i = 1; i < ans.size(); i++) cout << ' ' << (char) (ans[i] + 'A');
        cout << '\n';
        return; //退回
    }

    int flag; //判斷當前答案陣列能不能在擴展
    for(int i = 0; i < MAXN; i++){ //遍地搜尋
        flag = 1; 
        if(graph[i] != 1 || visit[i] == 1) continue; 
        //有被經歷過了或沒有這個節點(graph[i] != 1)
        for(auto it: ans){ //遍地搜尋 ans 有沒有都符合記錄關係
            if(order[it][i]){ //等於 1 表示沒有符合
                flag = 0; //退出 for，不能擴展繼續嘗試其他的節點
                break;
            }
        }

        if(flag == 1){ //表示此節點可以被擴展
            dfs(i);　//進入 DFS
            visit[i] = 0; //由於退回了，此節點要還原成原本狀態
            ans.pop_back();
        }
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> n; //輸入資料
    cin.ignore(); //為了後面的 getline，現在要讓指標先到下一行
    flag3 = 1;
    while(n--){
        string temp;
        getline(cin, temp); //replace blank line 把空白行消除掉
        getline(cin, temp); //輸入題目陣列
        //cout << "temp is " << temp << '\n';
        ss.clear(); ss.str(""); ss << temp; //給 stringstream 方便等等輸入資料
        memset(graph, 0, sizeof(graph)); //重新整理資料，避免干擾
        memset(order, 0, sizeof(order));
        lg = 0; //用來記錄題目陣列長度
        while(ss >> ch){ 
            graph[ch - 'A'] = 1; //把每個值 hash 成 字元 - 'A'，1 就是有這節點
            lg++; //長度增加
        }

        getline(cin, temp); //輸入記錄關係
        ss.clear(); ss.str(""); ss << temp; //給 stringstream 方便等等輸入資料
        while(ss >> temp) order[temp[2] - 'A'][temp[0] - 'A'] = 1;
        //由於記錄關係是用字串表達，且只會有一個字母，所以就用這樣記錄
        //需要提醒的是，我是記錄違法記錄關係的，也就是會把後面關係放在前面 index，前面關係放在後面
        //這樣只要 DFS 有掃到就可以表示不符合關係。
        //也有其他種寫法，可以自己嘗試

        flag2 = 1; //判斷有沒有拓樸排序
        if(flag3 == 0) cout << "\n"; //嚴格比較，每筆測資的斷航
        if(flag3) flag3 = 0; //第一筆沒有斷行，因此第二筆開始都是 0。
        for(int i = 0; i < MAXN; i++){ //遍地搜尋 
            if(graph[i] == 1){ //有此節點就繼續
                dfs(i); //擴展 DFS
                ans.pop_back(); //還原狀態
                visit[i] = 0;
            }
        }
        if(flag2) cout << "NO\n"; //如果沒有找到，就輸出 no


    }

    return 0;
}