단어 제한 끝말잇기

//
//  main.cpp
//  Wordchain
//
//  Created by  Heejun Lee on 7/21/17.
//  Copyright © 2017  Heejun Lee. All rights reserved.
//


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T,N;
vector<string> words;
vector<vector<int>> adj;
vector<int> checked;
vector<int> ordered;

void makeGraph(){
    adj = vector<vector<int>>(N,vector<int>(N,0));
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++){
            if(i==j) adj[i][j] = 0;
            else if(words[i].back() == words[j].front()) adj[i][j] = 1;
        }
}

int dfs(int here, int count){
    checked[here] = 1;
    int ret=0;
    if(count == N-1){
        ordered.push_back(here);
        return 1;
    }
    for(int there=0;there<N;there++)
        if(here != there && adj[here][there] && !checked[there]){
            ret = dfs(there, count+1);
            if(ret)
                ordered.push_back(here);
            else{
                checked[there]=0;
            }
        }
    return ret;
}

vector<int> topologySort(){
    for(int start=0;start<N;start++){
        checked.clear();
        checked = vector<int>(N,0);
        ordered.clear();
        if(dfs(start, 0) != 0) break;
    }
    if(ordered.empty()) return vector<int>();
    else return ordered;
}

int main() {
    cin >> T;
    while(T--){
        cin >> N;
        words = vector<string>(N);
        for(int i=0;i<N;i++)
            cin >> words[i];
        makeGraph();
        vector<int> ret = topologySort();
        reverse(ret.begin(), ret.end());
        if(ret.empty())
            cout << "IMPOSSIBLE" << endl;
        else{
            for(int i=0;i<ret.size();i++)
                cout << words[ret[i]] + " ";
            cout<<endl;
        }
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<vector<int>> adj;
vector<string> graph[26][26];
vector<int> indegree, outdegree;

void getEulerCircuit(int u, vector<int>& circuit){
    for (int v = 0; v < adj.size(); ++v){
        while (adj[u][v]>0){
            adj[u][v]--;
            getEulerCircuit(v, circuit);
        }
    }
    circuit.push_back(u);
}

vector<int> getEulerTrailOrCircuit(){
    vector<int> circuit;
    for (int i = 0; i < 26; ++i){
        if (outdegree[i] == indegree[i] + 1){ //    무조건 시작지점인 문자 있는 지 체크 후 그걸로 오일러트레일러 생성
            getEulerCircuit(i, circuit);
            return circuit;
        }
    }
    for (int i = 0; i < 26; ++i){ //    오일러서킷이므로 간선 있는 경우부터 시작
        if (outdegree[i]){
            getEulerCircuit(i,circuit);
            return circuit;
        }
    }
    return circuit;
}


void makeGraph(const vector<string>& words){
    for (int i = 0; i < 26; ++i){
        for (int j = 0; j < 26; ++j){
            graph[i][j].clear();
        }
    }
    adj = vector<vector<int>>(26,vector<int>(26,0));
    indegree = outdegree = vector<int>(26, 0);

    for (int i = 0; i < words.size(); ++i){
        int a = words[i][0] - 'a';
        int b = words[i][words[i].size() - 1] - 'a';
        graph[a][b].push_back(words[i]);
        adj[a][b]++;
        outdegree[a]++;
        indegree[b]++;
    }
}

bool checkEuler(){
    int plus1 = 0, minus1 = 0;
    for (int i = 0; i < 26; ++i){
        int delta = outdegree[i] - indegree[i];
        if (delta < -1 || delta > 1) return false;
        if (delta == 1) plus1++;
        if (delta == -1) minus1++;
    }
    //Euler Trail || Euler Circuit
    return (plus1 == 1 && minus1 == 1) || (plus1==0 && minus1==0);
}

string solve(const vector<string>& words){
    makeGraph(words);
    if (!checkEuler()) return "IMPOSSIBLE";

    vector<int> circuit = getEulerTrailOrCircuit();
    if (circuit.size() != words.size() + 1) return "IMPOSSIBLE";

    reverse(circuit.begin(), circuit.end());
    string ret;
    for (int i = 1; i < circuit.size(); ++i){
        int a = circuit[i - 1], b = circuit[i];
        if (ret.size()) ret += " ";
        ret += graph[a][b].back();
        graph[a][b].pop_back();
    }
    return ret;
}

int main(void){
    int C, N;
    cin >> C;

    for (int test = 1; test <= C; ++test){
        cin >> N;

        vector<string> words = vector<string>(N);
        char ch[11];
        for (int i = 0; i < N; ++i){
            getchar();
            scanf("%s", ch);
            words[i] = ch;
        }
        string str = solve(words);
        printf("%s\n", str.c_str());
    }
    return 0;
}