WORDCHAIN

문제출처 : https://algospot.com/judge/problem/read/WORDCHAIN

이 문제에서 얻어 갈 수 있는 것은 eulerian curcuit과 eulerian trail을 얻는 방법과

주어진 그래프에서 오일러 회로 및 트레일이 존재할 수 있는 여부를 따지는 방법에 대한 코드이다.

오일러 회로 및 트레일에 대한 설명은 여기서 얻을 수 있다.

구현된 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
 
using namespace std;
 
vector<string> dic[26][26];
vector<vector<int> > adj;
vector<int> indegree, outdegree;
vector<int> order;
 
void makeGraph(int n) {
    string str;
    adj = vector<vector<int> >(26, vector<int>(26, 0));
    indegree = vector<int>(26, 0);
    outdegree = vector<int>(26, 0);
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++)
            dic[i][j].clear();
    }
    while (n--) {
        cin >> str;
        int front = str.front() - 'a';
        int back = str.back() - 'a';
        dic[front][back].push_back(str);
        adj[front][back]++;
        indegree[back]++;
        outdegree[front]++;
    }
}
 
bool checkEuler() {
    int size = adj.size();
    int start = 0, end = 0;
    for (int i = 0; i < size; i++) {
        if (indegree[i] + 1 == outdegree[i])
            start++;
        else if (indegree[i] == outdegree[i] + 1)
            end++;
        else if (indegree[i] != outdegree[i])
            return false;
    }
    return (start == 1 && end == 1) || (start == 0 && end == 0);
}
 
void getEulerianPath(int here) {
    int size = adj.size();
    for (int there = 0; there < size; there++) {
        while (adj[here][there] > 0) {
            adj[here][there]--;
            getEulerianPath(there);
        }
    }
    order.push_back(here);
}
 
vector<int> getAnswerPath() {
    int size = adj.size();
    order.clear();
    if (checkEuler()) {
        for (int i = 0; i < size; i++) {
            if (indegree[i] + 1 == outdegree[i]) {
                getEulerianPath(i);
                reverse(order.begin(), order.end());
                return order;
            }
        }
        for (int i = 0; i < size; i++) {
            if (indegree[i]) {
                getEulerianPath(i);
                reverse(order.begin(), order.end());
                return order;
            }
 
        }
    }
    else {
        return order;
    }
}
 
string getAnswer() {
    vector<int> curcuit = getAnswerPath();
    if (curcuit.empty()) return "IMPOSSIBLE\n";
    else {
        string ans;
        for (int i = 0; i < curcuit.size()-1; i++){
            int ch_front = curcuit[i], ch_back = curcuit[i + 1];
            if (ans.size()) ans += " ";
            ans += dic[ch_front][ch_back].back();
            dic[ch_front][ch_back].pop_back();
        }
        ans += "\n";
        return ans;
    }
}
 
int main() {
    int C;
    cin >> C;
    while (C--) {
        int n; 
        cin >> n;
        makeGraph(n);
        string ans = getAnswer();
        cout << ans;
    }
}