題目大意：給一張無(wú)向圖，找一條字典序最小的歐拉路徑

題解：若圖不連通或有兩個(gè)以上的奇數(shù)點(diǎn)，則沒(méi)有歐拉路徑，可以$dfs$，在回溯時(shí)把這個(gè)節(jié)點(diǎn)加入答案

卡點(diǎn)：沒(méi)有在回溯時(shí)加入答案，導(dǎo)致出現(xiàn)了歐拉路徑?jīng)]走環(huán)（少走了一段）

?

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; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Memory-of-winter/p/10014705.html

總結(jié)

以上是生活随笔為你收集整理的[洛谷P1341]无序字母对的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。