[洛谷P1341]无序字母对

题目大意:给一张无向图,找一条字典序最小的欧拉路径

题解:若图不连通或有两个以上的奇数点,则没有欧拉路径,可以$dfs$,在回溯时把这个节点加入答案

卡点:没有在回溯时加入答案,导致出现了欧拉路径没走环(少走了一段)

 

C++ Code:

#include <cstdio>
#include <cctype>
#include <algorithm>
#define maxn 60
int m, start = 52, ind[maxn];
int v[maxn], n, ret[256];
bool e[maxn][maxn];
char ans[maxn * maxn]; int f[maxn];
int find(int x) {return x == f[x] ? x : (f[x] = find(f[x]));} void dfs(int u) {
for (int i = 1; i <= n; i++) if (e[u][i]) {
e[u][i] = e[i][u] = false;
dfs(i);
}
ans[m--] = v[u];
}
int main() {
scanf("%d", &m);
for (int i = 'A'; i <= 'Z'; i++) v[++n] = i, ret[i] = n;
for (int i = 'a'; i <= 'z'; i++) v[++n] = i, ret[i] = n;
for (int i = 1; i <= n; i++) f[i] = i;
for (int i = 0; i < m; i++) {
char ch = getchar();
while (!isalpha(ch)) ch = getchar();
int a = ret[static_cast<int> (ch)], b;
ch = getchar();
while (!isalpha(ch)) ch = getchar();
b = ret[static_cast<int> (ch)];
start = std::min(start, std::min(a, b));
e[a][b] = e[b][a] = true;
ind[a]++, ind[b]++;
f[find(a)] = find(b);
}
int cnt = 0;
for (int i = 1; i <= n; i++) if (ind[i] && f[i] == i) cnt++;
if (cnt > 1) {
puts("No Solution");
return 0;
}
cnt = 0;
for (int i = 1; i <= n; i++) if (ind[i] & 1) {
if (!cnt) start = i;
cnt++;
}
if (cnt > 2) {
puts("No Solution");
return 0;
} dfs(start);
puts(ans);
return 0;
}

  

上一篇:洛谷P1341 无序字母对【欧拉路】【dfs】


下一篇:java集合框架list和set