티스토리 뷰

Problem & Solving/Algospot

WORDCHAIN

성호스 2018. 2. 14. 16:56

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


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


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


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


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

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#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> >(26vector<int>(260));
    indegree = vector<int>(260);
    outdegree = vector<int>(260);
    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 = 0end = 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;
    }
}
cs


'Problem & Solving > Algospot' 카테고리의 다른 글

DICTIONARY  (0) 2018.01.24
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/02   »
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
글 보관함