\(POJ\) \(1041\) \(John's\) \(trip\)
一、题目大意
多组数据，输入\(x，y，z\)，表示结点\(x\)和结点\(y\)之间有一条序号为\(z\)的边，如果这个 无向图 中存在欧拉回路，就 输出字典序最小的欧拉回路，如果不存在欧拉回路就输出 Round trip does not exist. 。当输入0 0表示一组数据输入结束，题目保证了图的连通性。
给出一张无向图，要求从起点开始遍历一遍所有的边，最后再回到起点，题目要求输出任意一组方案
细节
-
起点不是点\(1\)，而是第一条边中两个端点中较小的一个点
-
给出的\(x\) \(y\) \(z\)代表的是点\(x\)到点\(y\)由\(id\)为\(z\)的边连接
-
最后答案要求输出的是边的\(id\)
二、解题思路
欧拉回路
对于一个图可以从一个顶点沿着边走下去，每个边只走一次，所有的边都经过后回到原点的路。
欧拉回路判定
- 无向图存在欧拉回路 \(\Leftrightarrow\) 每个顶点的度是偶数
- 有向图存在欧拉回路 \(\Leftrightarrow\) 每个顶点的出度等于入度（就是出去的边数等于进来的边数）
解题步骤
先根据欧拉路的定义判断是否存在欧拉路，如果存在的话再求字典序最小的欧拉路，一定是以边\(1\)为起始的欧拉路，然后将每个结点的边按序号从小到大排序，从而保证\(dfs\)的时候得到的是字典序最小的欧拉路。
题解:很明显的欧拉回路,首先判断是否为欧拉回路,即每个点的度都是偶数,如果满足欧拉回路,先对每个结点所连接的边按照边的编号排序,这里利用 vector 中的 pair是最好不过了.然后进行一次深搜就行了.
三、实现代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
typedef pair<int, int> PII;
const int N = 5010, M = N * N * 4;
int x, y, z, start, ed, cnt;
vector<PII> g[N]; // 一维：边号；二维：节点
int d[N]; // 度
bool st[N]; // 边是不是访问过
int ans[M], al; // 欧拉路径
void dfs(int u) {
for (int i = 0; i < g[u].size(); i++) { // 遍历u的每一条出边
if (st[g[u][i].first]) continue; // 如果此边已经访问过
st[g[u][i].first] = 1; // 标识此边已访问过
dfs(g[u][i].second); // 搜索下一个节点v
ans[++al] = g[u][i].first; // 记录边号id
}
}
void solve() {
for (int i = start; i <= ed; i++)
if (d[i] & 1) { // 无向图存在欧拉回路的充要条件是每个顶点的度是偶数
puts("Round trip does not exist.");
return; // 本次输入处理完毕
}
// 对于每个节点的每条出边，按边号由小到大排序,这样可以保证最终的欧拉回路路径字典序最小
for (int i = start; i <= ed; i++)
sort(g[i].begin(), g[i].end());
// 开始通过dfs搜索欧拉路径，因为起点是给定的，所以一路走回来，必然回到起点
dfs(start);
for (int i = al; i; i--) printf("%d ", ans[i]);
puts("");
}
int main() {
#ifndef ONLINE_JUDGE
freopen("POJ1041.in", "r", stdin);
#endif
while (true) {
memset(g, 0, sizeof g);
memset(d, 0, sizeof d); // 度初始化一下
memset(st, 0, sizeof st); // 边是否访问过的标识数组
al = 0; // 清空答案数组游标
// 本题的输入挺奇怪的，需要使用while(true)+do while的方式来读取最方便
scanf("%d%d", &x, &y);
if (x == 0 && y == 0) exit(0);
// 题目中规定了这是起点：起点不是点1，而是第一条边中两个端点中较小的一个点
start = min(x, y);
// 最大点号,预求最大，先设最小
ed = -1;
do {
scanf("%d", &z);
ed = max(ed, max(x, y));
d[x]++, d[y]++;
g[x].push_back(make_pair(z, y));
g[y].push_back(make_pair(z, x));
scanf("%d%d", &x, &y);
} while (x && y);
// 封装成solve是一个好习惯
solve();
}
return 0;
}