算法:欧拉路径
时间复杂度:$O(2^n)$
虽然 $N == 500$,但是不会达到 $2^N$,因为并不是该点于所有其它点都连接着边。
$root$ 求解的为起点,即度数为奇数的点,亦或编号较小且存在的度数的点。核心为求解 欧拉路径,采用回溯法求解逆序欧拉路径,每次优先搜索编号较小的点,再逆序输出即可。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, M = 1030;
int n = 500, m, cnt;
int g[N][N], d[N], ans[M];
void dfs(int u) // 求欧拉路径(回溯求路径)
{
for (int i = 1; i <= n; ++i) {
if (g[u][i]) {
g[u][i]--, g[i][u]--;
dfs(i);
}
}
ans[++cnt] = u;
}
int main()
{
cin >> m;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
g[a][b]++, g[b][a]++;
d[a]++, d[b]++;
}
int root = 0;
while (!d[root]) ++root; // 较小编号作为起点
for (int i = 1; i <= n; ++i) {
if (d[i] % 2) { // 奇数点作为起点
root = i;
break;
}
}
dfs(root);
for (int i = cnt; i >= 1; --i) cout << ans[i] << endl;
return 0;
}