分析
-
将栅栏的交点看成顶点,栅栏看成边,相当于给我们给我们一个无向图,让我们求一个欧拉路径。
-
题目要求输出字典序最小的一个,我们只需要保证从小到大考虑每个点即可。
-
当我们按照从小到大的顺序遍历所有点后,最终ans逆序后存储的是字典序最小的方案,这是因为如果先遍历1号点(编号从1到n),则1号点一定最后被加入欧拉路径。
-
另外我们还需要找到遍历的起点,首先要跳过孤立点,然后如果存在度数为奇数的点的话,从编号最小的奇数点开始dfs。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int n = 500, m; // n最大500, m边数
int g[N][N]; // g[i][j] = k,表示i到j有k条栅栏
int ans[1100], cnt; // 记录欧拉路径,最多1024条边
int d[N]; // 记录每个点的度
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 start = 1;
while (!d[start]) start++; // 跳过孤立点
for (int i = 1; i <= n; i++)
if (d[i] % 2) { // 题目保证一定有答案,如果存在度为奇数的点的话,只能存在2个
start = i;
break;
}
dfs(start);
for (int i = cnt; i; i--) printf("%d\n", ans[i]);
return 0;
}