[UVa] 872 Ordering.cpp

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

int Input(char []);
void Input2(char [], vector<int> [], int []);
bool backtracking(int, int, vector<int> [], int [], vector<int> &, char []);

int main()
{
    ios::sync_with_stdio(false);
    int Case;
    cin >> Case;
    while (Case--) {
        char Node_Name[30];         // 存每個Node的名稱('A','B',...)
        vector<int> toNxt[30];      // toNxt[i]表示i在哪些node的前面
        int beConnected[30] = {0};  // beConnected[i]表示有多少node在i前面
        vector<int> Container;      // backtracking存答案用

        // Input用來讀這個Case的第一行, Input2用來讀第二行
        int N = Input(Node_Name);        // N表示這個Case有幾個node
        sort(Node_Name, Node_Name + N); // 題目要求解答是字典序
        Input2(Node_Name, toNxt, beConnected);

        if (! backtracking(N, 0, toNxt, beConnected, Container, Node_Name))
            cout << "NO" << endl;

        if (Case) cout << endl;
    }
}
int Input(char Node[])
{
    int n = 0;
    stringstream SS;
    string Str;
    while (getline(cin, Str) && Str.empty());
    SS << Str;
    while (SS >> Node[n]) ++n;
    return n;
}
int find_position(char a, char Node_Name[])
{
    for (int i = 0; ; ++i)
        if (a == Node_Name[i])
            return i;
}
void Input2(char Node_Name[], vector<int> toNxt[], int beConnected[])
{
    stringstream SS;
    string Str;
    while (getline(cin, Str) && Str.empty());
    SS << Str;
    while (SS >> Str) {
        int a = find_position(Str[0], Node_Name);
        int b = find_position(Str[2], Node_Name);
        toNxt[a].push_back(b);
        ++beConnected[b];
    }
}
bool backtracking(int N, int Len, vector<int> toNxt[],
                  int beConnected[], vector<int> &Container, char Node[])
{
    if (Len == N){
        cout << Node[Container[0]];
        for (int i = 1; i < N; ++i)
            cout << ' ' << Node[Container[i]];
        cout << endl;
        return true;
    }
    bool ok ,hasAns = false;

    for (int i = 0; i < N; ++i) {
        if (beConnected[i] == 0) {
            Container.push_back(i);   // 將i放入解答
            --beConnected[i];         // 避免等等又選到i
            for (int nxt : toNxt[i])
                --beConnected[nxt];   // 將i連到的node --

            ok = backtracking(N, Len + 1, toNxt, beConnected, Container, Node);
            if (ok) hasAns = true;

            Container.pop_back();
            ++beConnected[i];
            for (int nxt : toNxt[i])
                ++beConnected[nxt];
        }
    }
    return hasAns;
}