P7771 【模板】欧拉路径

蒟蒻豆进阶之路 / 2023-08-04 / 原文

\(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\)

保证将有向边视为无向边后图连通。

链式前向星解法

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

const int N = 100010, M = N << 2;
typedef pair<int, int> PII;

int n, m; // n个节点,m条边
PII g[M]; // 用于排序边的临时数组

int start;           // 起点
int din[N], dout[N]; // 入度与出度
int ans[M], al;      // 记录欧拉路径
int tj[3];           // tj[0]:出度与入度不一致的数量;tj[1]:起点数量; tj[2]:终点数量

// 链式前向星
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++;
}

int st[M]; // 某条边是否已访问过
void dfs(int u) {
    for (int i = h[u]; ~i; i = h[u]) { // 删边,链表头指向了下一条边
        if (st[i]) {                   // i这条边已被访问过
            h[u] = ne[i];              // 删边,链表头指向了下一条边
            continue;
        }
        // 如果i这条边没有被访问过
        st[i] = 1;    // 标识已访问
        h[u] = ne[i]; // 跳到下一条边
        dfs(e[i]);    // 处理子节点
    }

    ans[++al] = u; // 这个点是在循环外加入路径的,注意,与边的那份代码可不一样啊!
}

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].first, &g[i].second); // 用一个PII(点对)的数组先把边保存下来,排序完后,再存入链式前向星中
    sort(g, g + m, greater<PII>());                                        // 一维由大到小排序,如果一维一样,那么二维也是由大到小排序。如此,则最后一个遍历到的就是字典序最小的

    for (int i = 0; i < m; i++) {
        add(g[i].first, g[i].second);           // 排序完再用链式前向星建图
        dout[g[i].first]++, din[g[i].second]++; // 有向图,维护入度和出度
    }

    int start = 1;
    for (int i = 1; i <= n; i++) {
        if (dout[i] != din[i]) tj[0]++;                // 出度入度不一致的数量
        if (dout[i] - din[i] == 1) tj[1]++, start = i; // 出度比入度大1的数量,一般理解为起点
        if (din[i] - dout[i] == 1) tj[2]++;            // 入度比出度大1的数量,一般理解为终点
    }
    // 有向图是否存在欧拉路径
    //  ① 如果所有点的出度入度全一致,则存在欧拉路径
    //  ② 如果所有的点出度入度不全一致,那么必须 出度-入度=1 和 入度-出度=1 的节点各有1个
    if (tj[0] && (tj[1] != 1 || tj[2] != 1)) {
        puts("No");
        return 0;
    }

    // 如果上面出现了环形的情况,那么start=0,此时,需要找出号最小的出发点,本题比较让人省心,直接写1就行了
    // 可是有的题不行,它规定最小的号不是1,而是10,所以,你只能再用循环,由小到大去找出号最小,而且有出边的节点
    // if (start == 0) {
    //     for (start = 1; start <= n; start++)
    //         if (~h[start]) break;
    // }

    dfs(start);

    // 查找欧拉路径
    // dfs(start);
    // 输出欧拉路径
    for (int i = al; i; i--) printf("%d ", ans[i]);
    return 0;
}

邻接表解法

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

const int N = 1e5 + 10, M = 2e5 + 10;

// 求有向图字典序最小的欧拉路径

int n, m;            // n个顶点,m条边
int din[N], dout[N]; // 入度、出度
vector<int> g[N];    // 邻接表
int ans[M], al;      // 结果数组
int tj[3];           // tj[0]:出度与入度不一致的数量;tj[1]:起点数量; tj[2]:终点数量

// h[u]是u的出边已经删了多少条,即走过多少条
int h[N];
void dfs(int u) {
    // 按指向点的字典序遍历出边,略过已经删掉的边
    for (int i = h[u]; i < g[u].size(); i = h[u]) {
        h[u]++;
        dfs(g[u][i]);
    }
    ans[++al] = u;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P7771.in", "r", stdin);
#endif
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d%d", &a, &b); // 有向图
        g[a].push_back(b);     // 记录a->b 有一条边
        dout[a]++, din[b]++;   // a出度+1, b入度+1
    }

    int start = 1;
    for (int i = 1; i <= n; i++) {
        if (dout[i] != din[i]) tj[0]++;                // 出度入度不一致的数量
        if (dout[i] - din[i] == 1) tj[1]++, start = i; // 起点数
        if (din[i] - dout[i] == 1) tj[2]++;            // 终点数
    }
    // 有向图是否存在欧拉路径
    //  ① 如果所有点的出度入度全一致,则存在欧拉路径
    //  ② 如果所有的点出度入度不全一致,那么必须 出度-入度=1 和 入度-出度=1 的节点各有1个
    if (tj[0] && (tj[1] != 1 || tj[2] != 1)) {
        puts("No");
        return 0;
    }
    // 为了完成字典序输出,需要对每个节点出发的边按对边点号由小到大进行排序
    for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());

    // 开始搜索欧拉路径
    dfs(start);

    // 输出欧拉路径
    for (int i = al; i; i--) printf("%d ", ans[i]);
    return 0;
}