[UVa] 200 Rare Order.cpp

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

vector<char> ans;
vector<char> toPoint[100];
int visit[100] = {0};
int deg[100] = {0}; // deg[i]=1:沒有被其他點連入 deg[i]=2:被其他點連入
void DFS(char n);

int main()
{
  //  freopen("input.txt","rt",stdin);
    ios::sync_with_stdio(false);
    string a, b;
    cin >> a;
    while (cin >> b && b != "#") {
        int L = (a.size() > b.size()) ? b.size() : a.size();
        for (int i = 0; i < L; ++i) {
            if (deg[a[i]] == 0) deg[a[i]] = 1;
            if (deg[b[i]] == 0) deg[b[i]] = 1;
            if (b[i] != a[i]) {
                toPoint[a[i]].push_back(b[i]);
                deg[b[i]] = 2;
                break;
            }
        }
        a = b;
    }
    for (char i = 'A'; i <= 'Z'; ++i)
        if (deg[i] == 1)
            DFS(i);

    for (auto iter = ans.rbegin(); iter != ans.rend(); ++iter)
        cout << *iter;
    cout << endl;
}
void DFS(char n)
{
    if (visit[n] == 1) return;
    visit[n] = 1;

    for (char nxt : toPoint[n])
        if (visit[nxt] != 2)
            DFS(nxt);
    visit[n] = 2;
    ans.push_back(n);
}