-
Notifications
You must be signed in to change notification settings - Fork 11
/
kattis_catenyms.cpp
107 lines (95 loc) · 3.2 KB
/
kattis_catenyms.cpp
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
/* Kattis - catenyms
A somewhat standard Eulerian path problem. Just note to sort the adjacency list lexicograhically
before we start the algorithm.
Observation 1:
We model each word u____v as an edge from u to v. There are thus 26 nodes with n edges in a
non-simple graph. We are trying to find an eulerian path within the graph. Check for both
cycles and non-cycles.
Time: O(V + E), Space: O(V + E)
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int num_tc, e, u, v, n = 26;
string s;
vector<pair<string, int>> adjlist[26];
vi in_deg, out_deg;
vector<pair<string, int>> hierholzer(int s) {
vi idx(n, 0);
vector<pair<string, int>> st;
vector<pair<string, int>> ans; // edge visiting, node
st.emplace_back("-", s);
while (!st.empty()) {
auto &[edge, u] = st.back();
if (idx[u] < (int)adjlist[u].size()) { // still has neighbor
st.push_back(adjlist[u][idx[u]]);
++idx[u];
} else {
ans.push_back(make_pair(edge, u));
st.pop_back();
}
}
reverse(ans.begin(), ans.end());
if ((int)ans.size() != e + 1) { // Eulerian path/cycle doesn't exist
return vector<pair<string, int>>();
}
return ans;
}
int main() {
cin >> num_tc;
for (int t = 0; t < num_tc; t++) {
cin >> e;
for (int i = 0; i < n; i++) adjlist[i].clear();
in_deg.assign(n, 0);
out_deg.assign(n, 0);
for (int i = 0; i < e; i++) {
cin >> s;
u = s[0] - 'a';
v = s.back() - 'a';
adjlist[u].push_back(make_pair(s, v));
in_deg[v]++;
out_deg[u]++;
}
for (int i = 0; i < 26; i++) {
sort(adjlist[i].begin(), adjlist[i].end());
}
// Check if there is a Eulerian path
int potential_start = 0, potential_end = 0, equal_in_out = 0;
int start_node = 0, equal_node = -1;
for (int i = 0; i < 26; i++) {
if (in_deg[i] + 1 == out_deg[i]) {
potential_start++;
start_node = i;
}
if (in_deg[i] == out_deg[i] + 1) {
potential_end++;
}
if (in_deg[i] == out_deg[i]) {
equal_in_out++;
// to know which node is part of the cycle
if (in_deg[i] > 0 && equal_node == -1) { // start from the earliest possible node
equal_node = i;
}
}
}
vector<pair<string, int>> ans;
if (equal_in_out == n) { // eulerian cycle present
ans = hierholzer(equal_node);
} else if (potential_start == 1 && potential_end == 1 &&
equal_in_out == n - 2) { // eulerian path present
ans = hierholzer(start_node);
}
if (ans.size() == 0) {
cout << "***" << endl;
continue;
}
for (int i = 1; i < (int)ans.size() - 1; i++) {
cout << ans[i].first << ".";
}
cout << ans.back().first << endl;
}
return 0;
}