UVa872 - Ordering(拓樸排序)

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