|
|
|
|
|
## [$UOJ$ $117$. 欧拉回路 ](https://uoj.ac/problem/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$），找环上一点或链的起点输出路径
|
|
|
|
|
|
|
|
|
|
|
|
- 无向图欧拉回路：图连通，一个环的情形（所有点度都为偶数），找环上一点输出路径
|
|
|
|
|
|
|
|
|
|
|
|
- 无向图欧拉路径：图连通，一个环或一条链的情形（所有点度都为偶数，或仅有恰有两个度数为奇数的点），找环上一点或链的一端输出路径
|
|
|
|
|
|
|
|
|
|
|
|
欧拉回路性质：可以被拆成若干个环
|
|
|
|
|
|
|
|
|
|
|
|
### 三、实现代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#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;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
