Solution
找一条字典序最小的欧拉路径.
用 $multiset$ 存储领接表.
欧拉路径模板传送门
Code
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<set>
- using namespace std;
- const int N = 1e3 + 5;
- int n, up = 'z' - 'A' + 1;
- int ans[N], tot, d[N], num;
- multiset<int> to[N];
- void dfs(int u) {
- multiset<int> :: iterator i;
- for (i = to[u].begin(); i != to[u].end(); i = to[u].begin()) {
- int nt = *i;
- to[nt].erase(to[nt].find(u));
- to[u].erase(to[u].find(nt));
- dfs(nt);
- }
- ans[++tot] = u;
- }
- int main()
- {
- scanf("%d", &n);
- for (int i = 1; i <= n; ++i) {
- char s[3];
- scanf("%s", s);
- to[s[0] - 'A' + 1].insert(s[1] - 'A' + 1);
- to[s[1] - 'A' + 1].insert(s[0] - 'A' + 1);
- d[s[1] - 'A' + 1]++;
- d[s[0] - 'A' + 1]++;
- }
- for (int i = 1; i <= up; ++i)
- if (d[i] & 1)
- num++;
- if (num == 1 || num> 2)
- return puts("No Solution"), 0;
- if (num == 0) {
- for (int i = 1; i <= up; ++i)
- if (d[i]) {dfs(i); break;}
- }
- else
- for (int i = 1; i <= up; ++i)
- if (d[i] && (d[i] & 1)) {dfs(i); break;}
- for (int i = tot; i; i--)
- putchar(ans[i] + 'A' - 1);
- puts("");
- }
- View Code
来源: http://www.bubuko.com/infodetail-2787492.html