A rare book collector recently discovered a book written in an unfamiliar language that used the same characters as the English language. The book contained a short index, but the ordering of the items in the index was different from what one would expect if the characters were ordered the same way as in the English alphabet. The collector tried to use the index to determine the ordering of characters (i.e., the collating sequence) of the strange alphabet, then gave up with frustration at the tedium of the task.
    You are to write a program to complete the collector’s work. In particular, your program will take a set of strings that has been sorted according to a particular collating sequence and determine what that sequence is.
Input
The input consists of an ordered list of strings of uppercase letters, one string per line. Each string contains at most 20 characters. The end of the list is signalled by a line with the single character ‘#’. Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used.
Output
Your output should be a single line containing uppercase letters in the order that specifies the collating sequence used to produce the input data file.
Sample Input
XWY
ZX
ZXY
ZXW
YWWX

Sample Output
XZYW

问题链接：UVA200 LA5139 Rare Order
问题简述：给定若干单词，这些单词是按某种字典顺序排列的，要求输出这些字母的顺序。
问题分析：用拓扑排序算法来解决。似乎DFS也可以， 参见程序代码。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序如下：

/* UVA200 LA5139 Rare Order */

#include <bits/stdc++.h>

using namespace std;

const int N = 26;
char a[N];
int g[N][N], din[N];
const int L = 20;
char s1[L + 1], s2[L + 1];

void toposort()
{
    queue<int> q;
    for(int i = 0; i < N; i++)
        if(a[i] && din[i] == 0) q.push(i);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        putchar('A' + u);
        for(int v = 0; v < N; v++)
            if(g[u][v] && din[v])
                if(--din[v] == 0) q.push(v);
    }
    putchar('\n');
}

int main()
{
    while(~scanf("%s", s1)) {
        memset(a, 0, sizeof(a));
        memset(g, 0, sizeof(g));
        memset(din, 0, sizeof(din));
        for(int i = 0; s1[i]; i++) a[s1[i] - 'A'] = 1;
        while(~scanf("%s", s2) && s2[0] != '#') {
            int len = min(strlen(s2), strlen(s1));
            for(int i = 0; i < len; i++)
                if(s1[i] != s2[i]) {
                    a[s1[i] - 'A'] = a[s2[i] - 'A'] = 1;
                    if(g[s1[i] - 'A'][s2[i] - 'A'] == 0) din[s2[i] - 'A']++;
                    g[s1[i] - 'A'][s2[i] - 'A'] = 1;
                    break;
                }
            memcpy(s1, s2, sizeof(s2));
        }

        toposort();
    }

    return 0;
}

AC的C++语言程序(DFS)如下：

/* UVA200 LA5139 Rare Order */

#include <bits/stdc++.h>

using namespace std;

const int N = 26;
char a[N], vis[N];
vector<int> g[N];
const int L = 20;
char s1[L + 1], s2[L + 1];
vector<int> order;

void dfs(int k)
{
    vis[k] = true;
    for (auto nk : g[k])
        if (vis[nk]) continue;
        else dfs(nk);
    order.push_back(k);
}

int main()
{
    while(~scanf("%s", s1)) {
        memset(a, 0, sizeof(a));
        for(int i = 0; i < N; i++) g[i].clear();
        while(~scanf("%s", s2) && s2[0] != '#') {
            int len = min(strlen(s2), strlen(s1));
            for(int i = 0; i < len; i++)
                if(s1[i] != s2[i]) {
                    a[s1[i] - 'A'] = a[s2[i] - 'A'] = 1;
                    g[s1[i] - 'A'].push_back(s2[i] - 'A');
                    break;
                }
            memcpy(s1, s2, sizeof(s2));
        }

        order.clear();
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < N; i++)
            if(a[i] && !vis[i]) dfs(i);
        for (int i = order.size() - 1; i >= 0; i--)
            putchar('A' + order[i]);
        putchar('\n');
    }

    return 0;
}

AC的C++语言程序如下：

/* UVA200 LA5139 Rare Order */

#include <bits/stdc++.h>

using namespace std;

const int N = 26;
char a[N];
int n, g[N][N], din[N];
map<char, int> m;
const int M = 100000;
const int L = 20;
char v[M][L + 1];
int lcnt;
queue<char> q;

void toposort()
{
    for(int i = 0; i < n; i++)
        if(din[m[a[i]]] == 0) q.push(a[i]);
    while(!q.empty()) {
        char t = q.front();
        q.pop();
        putchar(t);
        for(int i = 0; i < n; i++)
            if(g[m[t]][i] && din[i])
                if(--din[i] == 0) q.push(a[i]);
    }
    putchar('\n');
}

int main()
{
    lcnt = 0;
    while(~scanf("%s", v[lcnt]) && strcmp(v[lcnt], "#") != 0) lcnt++;

    memset(a, 0, sizeof(a));
    for(int i = 0; i < lcnt; i++)
        for(int j = 0; j < lcnt; j++)
            a[(int)v[i][j] - 'A'] = 1;
    n = 0;
    for(int i = 0; i < N; i++)
        if(a[i]) a[n++] = 'A' + i;

    sort(a, a + n);

    for(int i = 0; i < n; i++) m[a[i]] = i;

    memset(g, 0, sizeof(g));
    memset(din, 0, sizeof(din));
    for(int i = 0; i < lcnt; i++)
        for(int j = i + 1; j < lcnt; j++) {
            int minlen = min(strlen(v[i]), strlen(v[j]));
            for(int k = 0; k < minlen; k++)
                if(v[i][k] != v[j][k]) {
                    if(g[m[v[i][k]]][m[v[j][k]]] == 0) din[m[v[j][k]]]++;
                    g[m[v[i][k]]][m[v[j][k]]] = 1;
                    break;
                }
        }

    toposort();

    return 0;
}