[DICTIONARY] 고대어 사전

[DICTIONARY] 고대어 사전 : https://algospot.com/judge/problem/read/DICTIONARY

### 위상정렬 ###

<소스코드>

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        scanf("%d", &n);
        
        vector<string> v;
        for(int i=0; i<n; i++) {
            string s;
            cin >> s;
            v.push_back(s);
        }
 
        int ind[26]={0};
        vector<int> g[26];
        for(int i=1; i<n; i++) {
            int idx=0;
            while(v[i-1][idx] != 0 && v[i][idx] != 0) {
                if(v[i-1][idx] == v[i][idx]) idx++;
                else break;
            }
 
            if(v[i-1][idx] != 0 && v[i][idx] != 0) {
                g[v[i-1][idx]-'a'].push_back(v[i][idx]-'a');
                ind[v[i][idx]-'a']++;
            }
        }
 
        queue<int> q;
        for(int i=0; i<26; i++) {
            if(!ind[i])
                q.push(i);
        }
 
        vector<char> ans;
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            ans.push_back('a'+cur);
            
            for(int i=0; i<g[cur].size(); i++) {
                int next = g[cur][i];
                ind[next]--;
                if(!ind[next]) {
                    q.push(next);
                }
            }
        }
        
        if(ans.size() != 26) puts("INVALID HYPOTHESIS");
        else {
            for(int i=0; i<ans.size(); i++)
                printf("%c", ans[i]);
            puts("");
        }
    }
    return 0;
}

<예전에 AC 받은 코드> - 코드를 보면 종만북 솔루션으로 있는 코드같아 보인다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> order;
vector<bool> visited;
vector<vector<int> > v;
 
void makeGraph(const vector<string> &words)
{
    v = vector<vector<int> >(26, vector<int>(26, 0));
    for(int i=1; i<words.size(); i++) {
        int len = min(words[i-1].size(), words[i].size());
        for(int k=0; k<len; k++) {
            int a = words[i-1][k]-'a';
            int b = words[i][k]-'a';
            if(a != b) {
                v[a][b] = 1;
                break;
            }
        }
    }
}
 
void dfs(int s)
{
    visited[s] = 1;
    for(int i=0; i<v.size(); i++)
        if(v[s][i] && !visited[i])
            dfs(i);
    order.push_back(s);
}
 
vector<int> topologicalSort() {
    int i, j, n=v.size();
    visited = vector<bool>(n, 0);
    
    order.clear();
    for(i=0; i<n; i++)
        if(!visited[i])
            dfs(i);
    reverse(order.begin(), order.end());
    
    for(i=0; i<n; i++)
        for(j=i+1; j<n; j++)
            if(v[order[j]][order[i]])
                return vector<int>();
    return order;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        vector<string> words;
 
        scanf("%d", &n);
        while(n--) {
            string s;
            cin >> s;
            words.push_back(s);
        }
 
        makeGraph(words);
        vector<int> ans = topologicalSort();
 
        n = ans.size();
        if(!n)
            puts("INVALID HYPOTHESIS");
        else {
            for(int i=0; i<n; i++) {
                printf("%c", ans[i]+'a');
            }
            puts("");
        }
    }
 
}