POJ 1041 John's trip

\(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\)

二、解题思路

欧拉回路

对于一个图可以从一个顶点沿着边走下去，每个边只走一次，所有的边都经过后回到原点的路。

欧拉回路判定

解题步骤

先根据欧拉路的定义判断是否存在欧拉路，如果存在的话再求字典序最小的欧拉路，一定是以边\(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;
}