python/TangDou/AcWing/EulerPath/POJ1041.md

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的时候得到的是字典序最小的欧拉路。

解释：链式前向星是与dfs配合的，栈的原理，由大到小排序，最后走的就是小的，反着打出来就是由小到大

三、do \ while版本

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;

const int N = 2010, M = N * N;

// 声明结构体
struct Node {
    int a, b, c;
    bool const operator<(const Node &t) const {
        return c > t.c;
    }
} g[N];

int st[M];      // 某条边是不是访问过，无向图一般用于处理成对就换的边
int d[N];       // 度
int res[M], rl; // 路径数组
int m;          // m条边

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(int u) {
    for (int i = h[u]; ~i; i = h[u]) { // 删边优化
        h[u] = ne[i];
        if (st[i]) continue;
        st[i] = st[i ^ 1] = 1; // 成对变换
        dfs(e[i]);
        // 记录路径
        res[++rl] = w[i];
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ1041.in", "r", stdin);
#endif
    int a, b, c;

    while (true) {
        memset(d, 0, sizeof d);
        memset(st, 0, sizeof st);
        memset(h, -1, sizeof h);
        memset(res, 0, sizeof res);
        idx = rl = m = 0;

        // 本题的输入挺奇怪的，需要使用while(true)+do while的方式来读取最方便
        scanf("%d%d", &a, &b);
        if (a == 0 && b == 0) exit(0);

        do {
            scanf("%d", &c);
            g[m].a = a, g[m].b = b, g[m++].c = c;
            scanf("%d%d", &a, &b);
        } while (a && b);

        // 针对边的边号进行由小到大排序
        sort(g, g + m);

        for (int i = 0; i < m; i++) {
            int a = g[i].a, b = g[i].b, c = g[i].c;
            add(a, b, c), add(b, a, c);
            d[a]++, d[b]++;
        }

        int flag = 0;
        for (int i = 0; i < m; i++) {
            int a = g[i].a, b = g[i].b;
            if ((d[a] & 1) || (d[b] & 1)) {
                flag = 1;
                break;
            }
        }
        if (!flag) {
            dfs(1);
            // 逆序输出序列
            for (int i = rl; i; i--) printf("%d ", res[i]);
        } else
            cout << "Round trip does not exist.";
        puts("");
    }
    return 0;
}

四、while版本

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;

const int N = 2010, M = N * N;

// 声明结构体
struct Node {
    int a, b, c;
    bool const operator<(const Node &t) const {
        return c > t.c;
    }
} g[N];

int st[M];      // 某条边是不是访问过，无向图一般用于处理成对就换的边
int d[N];       // 度
int res[M], rl; // 路径数组
int m;          // m条边

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(int u) {
    for (int i = h[u]; ~i; i = h[u]) { // 删边优化
        h[u] = ne[i];
        if (st[i]) continue;
        st[i] = st[i ^ 1] = 1; // 成对变换
        dfs(e[i]);
        // 记录路径
        res[++rl] = w[i];
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ1041.in", "r", stdin);
#endif
    int a, b, c;

    while (true) {
        memset(d, 0, sizeof d);
        memset(st, 0, sizeof st);
        memset(h, -1, sizeof h);
        memset(res, 0, sizeof res);
        idx = rl = m = 0;

        scanf("%d%d", &a, &b);
        if (a == 0 && b == 0) exit(0);
        
        scanf("%d", &c);
        g[m].a = a, g[m].b = b, g[m++].c = c;
        while (true) {
            scanf("%d%d", &a, &b);
            if (a == 0 && b == 0) break;
            scanf("%d", &c);
            g[m].a = a, g[m].b = b, g[m++].c = c;
        }

        // 针对边的边号进行由小到大排序
        sort(g, g + m);

        for (int i = 0; i < m; i++) {
            int a = g[i].a, b = g[i].b, c = g[i].c;
            add(a, b, c), add(b, a, c);
            d[a]++, d[b]++;
        }

        int flag = 0;
        for (int i = 0; i < m; i++) {
            int a = g[i].a, b = g[i].b;
            if ((d[a] & 1) || (d[b] & 1)) {
                flag = 1;
                break;
            }
        }
        if (!flag) {
            dfs(1);
            // 逆序输出序列
            for (int i = rl; i; i--) printf("%d ", res[i]);
        } else
            cout << "Round trip does not exist.";
        puts("");
    }
    return 0;
}