algospot - wordchain

//Algospot - WORDCHAIN
 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
int N;
int sidx, eidx, tidx;
bool c_flag;
vector<int> icount, ocount;
vector<stack<string>> adj;
stack<string> ans;
 
void init()
{
    ans = stack<string>();
    sidx = eidx = -50;
    icount = ocount = vector<int>(26, 0);
    adj = vector<stack<string>>(26);
    cin >> N;
    string s;
    for (int i = 0; i < N; i++)
    {
        cin >> s;
        tidx = s[0]-'a';
        adj[s[0] - 'a'].push(s);
        ++icount[s[0] - 'a'];
        ++ocount[s[s.size() - 1] - 'a'];
    }
    for (int i = 0; i < 26; i++)
    {
        if (sidx + eidx >= -100)
        {
            if (icount[i] > ocount[i])
            {
                if (sidx == -50)
                    sidx = i;
                else
                    sidx = -1000;
            }
            else if(icount[i] < ocount[i])
            {
                if(eidx == -50)
                    eidx = i;
                else
                   eidx = -1000;
            }
        }
    }
    if(sidx + eidx >0 || sidx +eidx == -100)
        c_flag = true;
    else
        c_flag = false;
}
 
void dfs(int here)
{
    int there;
    string s;
    while(!adj[here].empty())
    {
        --N;
        s = adj[here].top(); adj[here].pop();
        there = s[s.size()-1];
        dfs(there-'a');
        ans.push(s);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int C;
    cin >> C;
    for (int t_num = 0; t_num < C; t_num++)
    {
        init();
        if(c_flag)
        {
            if(sidx == -50) sidx = tidx;
            dfs(sidx);
            if(N)
                c_flag = false;
        }
        if(c_flag)
            while(!ans.empty()){
                cout << ans.top() << " ";
                ans.pop();
            }
        else
            cout << "IMPOSSIBLE";
        cout << endl;
    }
}

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

algospot.com :: WORDCHAIN

 

Wordchain

한붓그리기인 오일러서킷/오일러트레일 문제입니다.

각 단어를 정점으로 하는 그래프가 아닌 각 단어를 간선으로 하고 시작/끝 알파벳을 정점으로 하는 그래프를 이용합니다.