DICTIONARY

출처: 알고스팟, 알고리즘 문제해결 전략2

AOJ DICTIONARY

SOL)
위상 정렬과, DFS를 이용한다.
주어진 단어를 가지고 adj를 만들고
DFS를 통해 위상 정렬 배열을 만든다.

만약 위상 정렬 배열 (x0, x1, x2 - - - xn)이 있을 때
adj[xi][xj]가 1이면 모순 이다. (단, i > j)

<소스 코드>

[-] Collapse

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

vector<vector<int> > adj;

void makeGraph(const vector<string>& words){
    adj = vector<vector<int> >(26, vector<int>(26, 0));
    for (int j = 1; j < words.size(); ++j) {
        int i = j - 1, len = min(words[i].size(), words[j].size());
        for (int k = 0; k < len; ++k){
            if (words[i][k] != words[j][k]) {
                int a = words[i][k] - 'a';
                int b = words[j][k] - 'a';
                adj[a][b] = 1;

                break;
            }
        }
    }
}

vector<int> seen, order;
void dfs(int here){
    seen[here] = 1;
    for (int there = 0; there < adj.size(); there++){
        if (adj[here][there] && !seen[there])
            dfs(there);
    }
    order.push_back(here);
}

vector<int> topologicalSort() {
    int n = adj.size();
    seen = vector<int>(n, 0);
    order.clear();
    for (int i = 0; i < n; i++) if (!seen[i]) dfs(i);
    reverse(order.begin(), order.end());
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++)
        //DAG가 아니라면 빈백터 리턴
        if (adj[order[j]][order[i]])
            return vector<int>();
    }
    return order;
}

int main(){
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        vector<string> str(n);

        for (int i = 0; i < n; i++)
            cin >> str[i];

        makeGraph(str);

        vector<int> ret = topologicalSort();
        if (ret.empty()) cout << "INVALID HYPOTHESIS";
        else{
            for (int i = 0; i < ret.size(); i++)
                cout << char(ret[i] + 'a');
        }
        cout << endl;
    }
}