python/TangDou/AcWing/EulerPath/UOJ117.md

UOJ 117. 欧拉回路

一、题目描述

时间限制：1s 空间限制：256MB

有一天，一位灵魂画师画了一张n个点m条边(1≤n≤1e5,0≤m≤2e5)的图。

现在要你找出 欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务：

这张图是无向图。（50分） 这张图是有向图。（50分） 图中可能有重边也可能有自环。

如果不可以一笔画，输出一行 NO。

否则，输出一行 YES，接下来一行输出一组方案。

如果 t=1，输出 m 个整数 p_1,p_2,…,p_m。令 e=∣p_i∣，那么 e 表示经过的第 i 条边的编号。如果 p_i为正数表示从 v_e 走到 u_e，否则表示从 u_e 走到 v_e。 如果 t=2，输出 m 个整数 p_1,p_2,…,p_m。其中 p_i 表示经过的第 i 条边的编号。

二、题目解析

经典Hierholzer算法，复杂度O(E)，判断存不存在，先判度，再判图是连通图

• 有向图欧拉回路：图连通，一个环的情形（所有点入度出度相等），找环上一点输出路径

• 有向图欧拉路径：图连通，一个环或一条链的情形（所有点入度出度相等，或仅有恰有两个点，其中一个入度=出度+1，另一个出度=入度+1），找环上一点或链的起点输出路径

• 无向图欧拉回路：图连通，一个环的情形（所有点度都为偶数），找环上一点输出路径

• 无向图欧拉路径：图连通，一个环或一条链的情形（所有点度都为偶数，或仅有恰有两个度数为奇数的点），找环上一点或链的一端输出路径

欧拉回路性质：可以被拆成若干个环

三、实现代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e5 + 10;
vector<PII> g[N];
int st[M];
int ans[M], al;
int din[N], dout[N];
int op, n, m;

// 需要删边优化
void dfs(int u) {
    while (g[u].size()) {
        PII x = g[u].back();
        g[u].pop_back();

        int v = x.first, id = x.second, fid = abs(id);
        if (st[fid]) continue;
        st[fid] = 1;
        dfs(v);
        ans[++al] = id; // 记录的是边号
    }
}
// 检查是不是存在欧拉回路
bool check() {
    int start = 1;
    if (op == 2) {
        for (int i = 1; i <= n; i++) {
            if (din[i] != dout[i]) return 0;
            if (din[i]) start = i;
        }
    } else {
        for (int i = 1; i <= n; i++) {
            if ((din[i] + dout[i]) & 1) return 0;
            if (din[i] + dout[i]) start = i;
        }
    }
    // 判连通，找出欧拉回路
    dfs(start);
    if (al < m) return 0;

    return 1;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("UOJ117.in", "r", stdin);
#endif

    scanf("%d %d %d", &op, &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].push_back({b, i});               // 对边点，边号
        if (op == 1) g[b].push_back({a, -i}); // 无向图
        din[b]++, dout[a]++;
    }

    if (!check()) {
        puts("NO");
        return 0;
    }

    puts("YES");
    for (int i = al; i; i--) printf("%d ", ans[i]);
    return 0;
}