끝말잇기 문제 (오일러 경로)

#include "stdafx.h"
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <string>
 
using namespace std;
 
void DFS(vector<vector<vector<string>>> & graph, vector<bool> &visited, int target) {
    visited[target] = true;
    // visit adjacent nodes
    for (int i = 0; i < 26; i++) {
        if (graph[target][i].size() != 0 && visited[i] == false) {
            DFS(graph, visited, i);
        }
    }
}
 
void eulerpath(vector<vector<vector<string>>> & graph, vector<string> & res, int target) {
    // go through adjacent nodes
    stack<string> buffer;
    for (int i = 0; i < 26; i++) {
        while (graph[target][i].size() != 0) {
            buffer.push(graph[target][i][graph[target][i].size() - 1]);
            graph[target][i].pop_back();
            eulerpath(graph, res, i);
        }
    }
    while (buffer.size() != 0) {
        res.push_back(buffer.top());
        buffer.pop();
    }
}
 
void tictactoe(vector<string> & data) {
    // make graph
    vector<vector<vector<string>>> graph(26, vector<vector<string>>(26, vector<string>()));
    vector<int> inbound(26, 0);
    vector<int> outbound(26, 0);
    for (int i = 0; i < data.size(); i++) {
        int from = data[i][0]-'a';
        int to = data[i][data[i].size() - 1]-'a';
        graph[from][to].push_back(data[i]);
        outbound[from]++;
        inbound[to]++;
    }
 
    // check if graph is seperated
    vector<bool> visited(26, false);
    int count = 0;
    int point = 0;
    for (int i = 0; i < 26; i++) {
        if (inbound[i]!=0&&outbound[i]!=0&&visited[i] == false) {
            point = i;
            count++;
            DFS(graph, visited, i);
        }
    }
    if (count != 1) {
        cout << "IMPOSSIBLE1" << endl;
        return;
    }
 
    // check if trail or cycle is possible
    int sc = 0;
    int start = 0;
    int lc = 0;
    int end = 0;
    for (int i = 0; i < 26; i++) {
        if (outbound[i] == inbound[i]) {
 
        }
        else if (outbound[i] == inbound[i] + 1) {
            lc++;
            start = i;
        }
        else if (outbound[i] + 1 == inbound[i]) {
            sc++;
            end = i;
        }
        else {
            cout << "IMPOSSIBLE2" << endl;
            return;
        }
    }
    // if lc or sc not balanced, return impossible
    vector<string> res;
    if (lc == 0 && sc == 0) {
        // euler cycle. start anywhere
        eulerpath(graph, res, point);
    }
    else if (lc == 1 && sc == 1) {
        // euler trail, start from start element
        graph[start][end].push_back("eraseme");
        eulerpath(graph, res, start);
        // erase eraseme
        for (int i = 0; i < res.size(); i++) {
            if (res[i] == "eraseme") {
                res.erase(res.begin() + i);
                break;
            }
        }
    }
    else {
        // not possible
        cout << "IMPOSSIBLE3" << endl;
        return;
    }
    reverse(res.begin(), res.end());
    for (string x : res) {
        cout << x << endl;
    }
}
 
int main() {
    vector<string> data = { "dog","god","dragon","need" };
    tictactoe(data);
    while(1){}
    return 0;
}