2848 - 고창어

https://www.acmicpc.net/problem/2848

그냥 쭉 쓰다보니 코드가 너무 길어졌다.
새로 정의한 사전순 문자열로부터 문자의 순서를 재정의한다.
예제 같은 경우는 l->u, l->k, u->k, k->a 이렇게 4개

1. 올바른 순서가 없는 경우
 : 모순이 존재한다는 것. 싸이클이 있다는 것이다.
 : 플로이드 돌린 후에 다시 자신으로 돌아오는 경로가 있으면 싸이클임.

2. 가능한 순서가 여러개인 경우
 : 사전의 첫 글자가 여러개이거나, (첫 글자로부터) k번째 숫자에 올 수 있는 수가 여러개인 경우.

위에 적은 것만 구현했는데 코드가 1.6KB나 된다. 소스 정말 더럽다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

int main(){
    int n;
    scanf("%d ", &n);
    bool used[26]={};
    bool v[26][26]={};
    char s[100][11];
    for(int i=0; i<n; ++i){
        scanf("%s ", s[i]);
        int clen = strlen(s[i]);
        for(int j=0; j<clen; ++j) used[s[i][j]-'a'] = true;
        if(i == 0) continue;
        int len = min(clen, (int)strlen(s[i-1]));
        for(int j=0; j<len; ++j){
            if(s[i-1][j] != s[i][j]){
                v[s[i-1][j]-'a'][s[i][j]-'a'] = true;
                break;
            }
        }
    }
   
    for(int k=0; k<26; ++k){
        for(int i=0; i<26; ++i){
            for(int j=0; j<26; ++j){
                v[i][j] |= v[i][k] & v[k][j];
            }
        }
    }
   
    // contradiction
    for(int i=0; i<26; ++i)
        if(v[i][i]) return puts("!"), 0;
   
    vector<int> start;
    for(int i=0; i<26; ++i){
        if(!used[i]) continue;
        bool hasIndegree = false;
        for(int j=0; j<26; ++j) hasIndegree |= v[j][i];
        if(!hasIndegree) start.push_back(i);
    }
   
    if(start.size() > 1) return puts("?"), 0;
   
    int dist = 1;
    vector<pair<int, char>> res(26, {0, 0});
    for(int i=0; i<26; ++i) res[i].second = i+'a';
    queue<int> q;
    q.push(start[0]);
    res[start[0]].first = dist++;
    while(!q.empty()){
        int qs = q.size();
        while(qs--){
            int cur = q.front();
            q.pop();
            for(int i=0; i<26; ++i){
                if(v[cur][i] && dist > res[i].first){
                    q.push(i);
                    res[i].first = dist;
                }
            }
        }
        dist++;
    }
   
    sort(res.begin(), res.end());
    for(int i=1; i<res.size(); ++i){
        if(res[i].first > 0 && res[i-1].first == res[i].first)
            return puts("?"), 0;
    }
    for(int i=0; i<res.size(); ++i){
        if(res[i].first > 0) putchar(res[i].second);
    }
   
    return 0;
}