Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 Shiritori

Category: JOI Tag: euler-path, graph

Shiritori

問題概要


2桁の数字で文字を表す.
この5文字の単語(つまり10桁の数字)でしりとりをする.
いまN個の単語が与えられるのでそれ全てを使うようなしりとりを答えろ.
複数ある場合は辞書順最小のものを答えろ

解法


各単語の最初の文字から最後の文字への有向辺を考える.
この有向グラフ上の辞書順最小のオイラー路を考えれば良い.
辞書順は辺を見る順を辞書順にするだけで達成できる.

連結なグラフがオイラー路を持つ条件は以下の2つどちらかを満たすこと

  • 各頂点の入力辺の数と出力辺の数が等しい(オイラー閉路をもつ)

  • 始点の出力辺の数が入力辺より1つ多く, 終点の入力辺の数が出力辺より1つ多く, その他の頂点は入力辺と出力辺の数が等しい

今回の問題ではそもそも連結にならない可能性があることにも注意すること.
オイラー閉路をもつ場合は始点を辞書順最小の頂点にする.
あとは有向グラフをdfsで潜っていき, 辺を戻るときにその辺に対応する単語を答えの頭に追加していけばよい.

コード


(shiritori.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n, deg[128], itr[128];
vector<string> words, ans;
vector<pii> G[128];

int find_start()
{
        vector<int> hs, ts;
        for (int i = 0; i < 100; i++) {
                if(deg[i] > 1) return -1;
                if(deg[i] == 1) hs.push_back(i);
                if(deg[i] == -1) ts.push_back(i);
        }
        if(hs.size() == 0 and ts.size() == 0) return stoi(words[0].substr(0,2));
        if(hs.size() != 1 or ts.size() != 1) return -1;
        return hs[0];
}

void build_graph()
{
        int i = 0;
        for(auto &w: words) {
                int u = stoi(w.substr(0,2)), v = stoi(w.substr(8,2));
                G[u].push_back(pii(v,i++));
        }
}

void euler(int v)
{
        for (int &i = itr[v]; i < (int)G[v].size();) {
                int j = i++;
                euler(G[v][j].first);
                ans.push_back(words[G[v][j].second]);
        }
}

int solve()
{
        sort(begin(words),end(words));
        int s = find_start();
        if(s < 0) return 0;
        build_graph();
        euler(s);
        if((int)ans.size() != n) return 0;
        reverse(begin(ans),end(ans));
        for(auto &e: ans) cout << e << endl;
        return 1;
}

void input()
{
        cin >> n;
        string s;
        for (int i = 0; i < n; i++) {
                cin >> s;
                words.push_back(s);
                deg[stoi(s.substr(0,2))]++;
                deg[stoi(s.substr(8,2))]--;
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        if(!solve()) cout << "impossible" << endl;
        return 0;
}

Comments