|
|
# [$P7771$ 【模板】欧拉路径](https://www.luogu.com.cn/problem/P7771)
|
|
|
|
|
|
## 题目描述
|
|
|
|
|
|
求有向图字典序最小的欧拉路径。
|
|
|
|
|
|
## 输入格式
|
|
|
|
|
|
第一行两个整数 $n,m$ 表示有向图的点数和边数。
|
|
|
|
|
|
接下来 $m$ 行每行两个整数 $u,v$ 表示存在一条 $u\to v$ 的有向边。
|
|
|
|
|
|
## 输出格式
|
|
|
|
|
|
如果不存在欧拉路径，输出一行 `No`。
|
|
|
|
|
|
否则输出一行 $m+1$ 个数字，表示字典序最小的欧拉路径。
|
|
|
|
|
|
## 样例 #1
|
|
|
|
|
|
### 样例输入 #1
|
|
|
|
|
|
```
|
|
|
4 6
|
|
|
1 3
|
|
|
2 1
|
|
|
4 2
|
|
|
3 3
|
|
|
1 2
|
|
|
3 4
|
|
|
```
|
|
|
|
|
|
### 样例输出 #1
|
|
|
|
|
|
```
|
|
|
1 2 1 3 3 4 2
|
|
|
```
|
|
|
|
|
|
## 样例 #2
|
|
|
|
|
|
### 样例输入 #2
|
|
|
|
|
|
```
|
|
|
5 5
|
|
|
1 2
|
|
|
3 5
|
|
|
4 3
|
|
|
3 4
|
|
|
2 3
|
|
|
```
|
|
|
|
|
|
### 样例输出 #2
|
|
|
|
|
|
```
|
|
|
1 2 3 4 3 5
|
|
|
```
|
|
|
|
|
|
## 样例 #3
|
|
|
|
|
|
### 样例输入 #3
|
|
|
|
|
|
```
|
|
|
4 3
|
|
|
1 2
|
|
|
1 3
|
|
|
1 4
|
|
|
```
|
|
|
|
|
|
### 样例输出 #3
|
|
|
|
|
|
```
|
|
|
No
|
|
|
```
|
|
|
|
|
|
## 提示
|
|
|
|
|
|
对于 $50\%$ 的数据，$n,m\leq 10^3$。
|
|
|
|
|
|
对于 $100\%$ 的数据，$1\leq u,v\leq n\leq 10^5$，$m\leq 2\times 10^5$。
|
|
|
|
|
|
保证将有向边视为无向边后图连通。
|
|
|
|
|
|
### $Code$
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 100010, M = N << 2;
|
|
|
typedef pair<int, int> PII;
|
|
|
#define a first
|
|
|
#define b second
|
|
|
|
|
|
int n, m; // n个节点，m条边
|
|
|
PII g[M]; // 用于排序边的临时数组
|
|
|
|
|
|
int start; // 起点
|
|
|
int din[N], dout[N]; // 入度与出度
|
|
|
int res[M], rl; // 记录欧拉路径
|
|
|
|
|
|
// 链式前向星
|
|
|
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]; // 删边，链表头指向了下一条边
|
|
|
dfs(e[i]); // 处理子节点
|
|
|
}
|
|
|
res[++rl] = u; // 这个点是在循环外加入路径的，注意，与边的那份代码可不一样啊！
|
|
|
}
|
|
|
|
|
|
// 黄海总结的有向图找起点的代码模板，注意每题中起始和终止不一样，i=0,还是i=1需要根据题目而定
|
|
|
int getStart() {
|
|
|
int st = 0, a = 0, b = 0, c = 0;
|
|
|
for (int i = 1; i <= n; i++) { // 枚举每个有效节点,每道题的具体实现可能有差异
|
|
|
if (dout[i] != din[i]) a++; // 出度与入度不一致的数量
|
|
|
if (dout[i] == din[i] + 1) b++, st = i; // 起点数量，记录起点
|
|
|
if (dout[i] == din[i] - 1) c++; // 终点数量
|
|
|
}
|
|
|
if (a && (b != 1 || c != 1)) return -1; // 如果有不一致的，并且不是1个，则没有欧拉路径
|
|
|
// 如果是一个环，也是存在欧拉路径的，但所有点的入度和出度一致，st不会被改写，需要再手找出起点。
|
|
|
while (!dout[st]) st++;
|
|
|
return st;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("P7771.in", "r", stdin);
|
|
|
#endif
|
|
|
// 初始化链式前向星
|
|
|
memset(h, -1, sizeof h);
|
|
|
// n个顶点，m条边
|
|
|
scanf("%d %d", &n, &m);
|
|
|
|
|
|
for (int i = 0; i < m; i++) scanf("%d %d", &g[i].a, &g[i].b); // 用一个PII(点对)的数组先把边保存下来，排序完后，再存入链式前向星中
|
|
|
sort(g, g + m, greater<PII>()); // 一维由大到小排序，如果一维一样，那么二维也是由大到小排序。如此，则最后一个遍历到的就是字典序最小的
|
|
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
|
add(g[i].a, g[i].b); // 排序完再用链式前向星建图
|
|
|
dout[g[i].a]++, din[g[i].b]++; // 有向图，维护入度和出度
|
|
|
}
|
|
|
|
|
|
int start = getStart();
|
|
|
if (start == -1) {
|
|
|
puts("No");
|
|
|
return 0;
|
|
|
}
|
|
|
dfs(start);
|
|
|
|
|
|
// 输出欧拉路径
|
|
|
for (int i = rl; i; i--) printf("%d ", res[i]);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
