python/TangDou/AcWing/EulerPath/P7771.md

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

#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;
}