algospot - dictionary

 

dictionary를 풀어보았습니다.

dfs를 이용한 위상정렬로 해결할수 있었습니다!

 

https://algospot.com/judge/problem/read/DICTIONARY

algospot.com :: DICTIONARY

 

//Algospot - DICTIONARY
 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
int C, N;
vector<vector<char>> adj;
vector<string> bucket;
vector<bool> visit;
vector<bool> termi;
stack<char> Stack;
bool a_flag;
bool check[26][26];
 
void init()
{
    cin >> N;
    adj = vector<vector<char>>(26);
    bucket = vector<string>(N);
    for (int i = 0; i < N; i++)
        cin >> bucket[i];
    visit = termi = vector<bool>(26, false);
    a_flag = true;
    for (int i = 0; i < 26; i++)
        for (int j = 0; j < 26; j++)
            check[i][j] = false;
    Stack = stack<char>();
}
 
void makeGraph()
{
    for (int i = 1; i < N; i++)
    {
        //abcd abc 와 같이 input이 들어오기 떄문에 더 작은 길이를 골라줍니다.
        int len = min(bucket[i - 1].size(), bucket[i].size());
        for (int j = 0; j < len; j++)
            if (bucket[i - 1][j] != bucket[i][j])
            {
                if (check[bucket[i - 1][j] - 'a'][bucket[i][j] - 'a'] == false)
                {
                    check[bucket[i - 1][j] - 'a'][bucket[i][j] - 'a'] = true;
                    adj[bucket[i - 1][j] - 'a'].push_back(bucket[i][j] - 'a');
                }
                break;
            }
    }
}
 
void dfs(int here)
{
    visit[here] = true;
    int there;
    for (int i = 0; i < adj[here].size(); i++)
    {
        there = adj[here][i];
        if (!visit[there])
            dfs(there);
        //이 경우는 싸이클이 생기는 경우입니다. a_flag를 false로 만들어 처리합니다!
        else if (!termi[there])
            a_flag = false;
    }
    termi[here] = true;
    Stack.push((char)('a' + here));
}
 
void dfsAll()
{
    for (int i = 0; i < 26; i++)
        if (a_flag && adj[i].size() != 0 && !visit[i])
            dfs(i);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> C;
    for (int i = 0; i < C; i++)
    {
        init();
        makeGraph();
        dfsAll();
        if (!a_flag)
            cout << "INVALID HYPOTHESIS" << endl;
        else
        {
            while (!Stack.empty())
            {
                cout << Stack.top();
                Stack.pop();
            }
            for (int i = 0; i < 26; i++)
                if (!visit[i])
                    cout << (char)('a' + i);
            cout << endl;
        }
    }
}