本题涉及欧拉回路/欧拉路径。
参考:https://blog.csdn.net/qq_34454069/article/details/77779300
http://www.cnblogs.com/zmin/p/6947266.html
https://www.cnblogs.com/shao0099876/p/7366852.html
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 | #include<iostream> #include<algorithm> #include<vector> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int n; struct e { char t; int bool_v; e(char t1, int v1) { t = t1; bool_v = v1; } bool operator < (const e& e2) const { return t < e2.t; } }; vector<e> edge[130]; vector<char> path; int degree[130]; bool visited[3000]; void dfs(char node) { for (int i = 0; i < edge[node].size(); i++) { if (visited[edge[node][i].bool_v])continue; visited[edge[node][i].bool_v] = true; dfs(edge[node][i].t); } path.push_back(node); } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) { char c1, c2; cin >> c1 >> c2; degree[c1]++; degree[c2]++; edge[c1].push_back(e(c2, i)); edge[c2].push_back(e(c1, i)); } for (char i = 0; i <= 126; i++) { if (edge[i].size() > 1)sort(edge[i].begin(), edge[i].end()); } int odd = 0;//奇 char s = -1; for (char i = 127; i >= 0; i--) { if (degree[i] % 2 == 0 && degree[i] > 0) { if (odd == 0)s = i; } else if (degree[i] % 2 == 1) { odd++; s = i; } } if (!(odd == 0 || odd == 2)) { cout << "No Solution"; return 0; } dfs(s); for (int i = path.size() - 1; i >= 0; i--) { cout << path[i]; } } |