\(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;
}