題目： UVa - 872 - Ordering

題目說明

給一些字母，及一些規則，如 A < B，表示 B 一定要排在 A 後面。求符合規則所有排序情況，並依照字典序輸出。

Input： 第一行為一整數，代表有幾組測資，每組測資的第一行為所有字母 ( 中間以空格隔開 )，第二行為排序規則 ( 一定是 < 的形式，中間以空格隔開 )。每組測資中間以空行隔開，整數及第一筆測資間也以空行隔開。

Output： 輸出所有排序情況並按照字典序排序。

解題思路

讀取所有字母並按照字典序排序 ( 確保後面做 DFS 時先輸出的會是字典序較小的 )，之後讀取規則，將 G[A][B] 設為 1 表示 A 指向 B，…，以此類推來建圖，之後 DFS 做 Topological Sort，同時搭配 Back Tracking 來排出所有情況即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <sstream>

#define FOR(i, n) for(int i = 0; i < n; ++i)
#define diff(ch) (ch - 'A')
#define SIZE(c) int(c.size())

using namespace std;

// reference: https://ppt.cc/fqUhHx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

auto print = [](string& str)
{
    cout << str[0];
    for (int i = 1; i < SIZE(str); ++i) cout << " " << str[i];
    cout << '\n';
};

int main()
{
    // Data
    int G[26][26];
    int visited[26];
    bool track;

    int T;
    string str, S;
    cin >> T;
    cin.ignore();

    function<void(string)> dfs = [&](string ret)
    {
        if (ret.length() == S.length()) { print(ret), track = true; return; }

        FOR(i, SIZE(S))
        {
            if (visited[diff(S[i])]) continue;
            
            int j = 0;
            for (; j < SIZE(ret); ++j) if (G[diff(S[i])][diff(ret[j])]) break;
            
            // 如果 j 不等於 ret 的長度表示 ret 裡面出現了必須要出現在 s[i] 後面的字元
            if (j != SIZE(ret)) continue;

            // back tracking
            visited[diff(S[i])] = 1;
            dfs(ret + S[i]);
            visited[diff(S[i])] = 0;
        }
    };

    while (T--)
    {
        getline(cin, str); // avoid space

        // init
        track = false;
        fill(G[0], G[0] + 676, 0);
        fill(visited, visited + 26, 0);
        S.clear();

        // 讀取英文字母
        getline(cin, str);
        stringstream ss(str);
        while (ss >> str) S += str;
        sort(begin(S), end(S));

        getline(cin, str);
        ss.clear();
        ss.str(str);
        // 紀錄不能出現在 str[0] 前面的字元
        while (ss >> str) G[diff(str[0])][diff(str[2])] = 1;

        dfs("");

        if (!track) cout << "NO\n";
        if (T) cout << '\n';
    }
}

參考資料

872 - Ordering.cpp