[洛谷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;

}