티스토리 뷰
문제출처 : 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> >(26, vector<int>(26, 0)); indegree = vector<int>(26, 0); outdegree = vector<int>(26, 0); 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 = 0, end = 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 |
---|
댓글