【模板】欧拉路径

GitHub 跳转原题关系图返回列表

先判定有向欧拉路存在条件，再把每个点的出边按升序走 Hierholzer，最后逆序得到字典序最小的欧拉路径。

OJ: luogu

题目 ID: P7771

难度:普及+/提高

标签:图论欧拉路贪心模板题

日期: 2026-06-19 23:56

题意

给一张有向图，要求输出一条字典序最小的欧拉路径。

也就是：

每条边恰好走一次
输出经过的顶点序列
如果不存在这样的路径，输出 No

样例图

这张图展示样例 2 的结构：

digraph G {
  rankdir=LR;
  1 -> 2;
  2 -> 3;
  3 -> 4;
  4 -> 3;
  3 -> 5;
}

从 3 出发时，既可以去 4，也可以去 5。为了让最终顶点序列字典序最小，应该优先走向编号更小的 4，于是答案是 1 2 3 4 3 5。这说明除了判定欧拉路存在，还要额外处理“出边按什么顺序走”。

思路

先看一个小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXM = 20;

int n, m;
int eu[MAXM], ev[MAXM];
vector<int> out_edges[MAXN];
bool used[MAXM];
vector<int> cur_path, best_path;

bool better(const vector<int> &a, const vector<int> &b) {
    if (b.empty()) {
        return true;
    }
    for (int i = 0; i < (int) a.size(); i++) {
        if (a[i] != b[i]) {
            return a[i] < b[i];
        }
    }
    return false;
}

void dfs(int u, int used_cnt) {
    if (used_cnt == m) {
        if (better(cur_path, best_path)) {
            best_path = cur_path;
        }
        return;
    }

    for (int id : out_edges[u]) {
        if (used[id]) {
            continue;
        }
        used[id] = true;
        cur_path.push_back(ev[id]);
        dfs(ev[id], used_cnt + 1);
        cur_path.pop_back();
        used[id] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        out_edges[i].clear();
    }

    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        out_edges[eu[i]].push_back(i);
        used[i] = false;
    }

    for (int i = 1; i <= n; i++) {
        sort(out_edges[i].begin(), out_edges[i].end(), [&](int x, int y) {
            if (ev[x] != ev[y]) {
                return ev[x] < ev[y];
            }
            return x < y;
        });
    }

    best_path.clear();
    for (int start = 1; start <= n; start++) {
        cur_path.clear();
        cur_path.push_back(start);
        dfs(start, 0);
    }

    if (best_path.empty()) {
        cout << "No\n";
    } else {
        for (int i = 0; i < (int) best_path.size(); i++) {
            if (i) {
                cout << ' ';
            }
            cout << best_path[i];
        }
        cout << '\n';
    }

    return 0;
}

暴力直接枚举所有可能的走法：

从每个点尝试作为起点
每次任选一条还没用过的出边继续走
如果最后恰好用完全部边，就得到一条候选欧拉路径
在这些候选里取字典序最小

这个办法只能验证小数据，正式做法要用 Hierholzer。

先回顾有向欧拉路的存在条件：

把有向边看成无向边后，所有有边的点要连通
度数满足以下两种之一：
- 所有点 in = out，存在欧拉回路
- 恰有一个点满足 out = in + 1，作为起点
- 恰有一个点满足 in = out + 1，作为终点

有了解的判定后，再考虑字典序。

Hierholzer 的特点是：

走边时先不输出
回溯时再把点放进答案
所以答案会倒着产生

为了让最终答案字典序最小，只要让每个点总是优先走向编号更小的后继即可。

实现上：

每个点的出边按终点升序排序
用栈模拟 Hierholzer
当前点还有边，就沿最小的那条边继续走
当前点没边了，就把它放进 path
最后把 path 倒着输出

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, m;
vector<int> graph[MAXN];
vector<int> weak[MAXN];
int indeg[MAXN], outdeg[MAXN], iter_[MAXN];
vector<int> path;

bool check_connected() {
    int start = 0;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] + outdeg[i] > 0) {
            start = i;
            break;
        }
    }

    if (start == 0) {
        return true;
    }

    vector<int> vis(n + 1, 0);
    stack<int> st;
    st.push(start);
    vis[start] = 1;

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        for (int v : weak[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                st.push(v);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (indeg[i] + outdeg[i] > 0 && !vis[i]) {
            return false;
        }
    }
    return true;
}

int find_start() {
    int start_cnt = 0, end_cnt = 0;
    int start = 0;

    for (int i = 1; i <= n; i++) {
        if (outdeg[i] == indeg[i] + 1) {
            start_cnt++;
            start = i;
        } else if (indeg[i] == outdeg[i] + 1) {
            end_cnt++;
        } else if (indeg[i] != outdeg[i]) {
            return -1;
        }
    }

    if (start_cnt == 1 && end_cnt == 1) {
        return start;
    }
    if (start_cnt == 0 && end_cnt == 0) {
        for (int i = 1; i <= n; i++) {
            if (outdeg[i] > 0) {
                return i;
            }
        }
        return 1;
    }
    return -1;
}

void hierholzer(int start) {
    vector<int> st;
    st.push_back(start);

    while (!st.empty()) {
        int u = st.back();
        if (iter_[u] < (int) graph[u].size()) {
            int v = graph[u][iter_[u]++];
            st.push_back(v);
        } else {
            path.push_back(u);
            st.pop_back();
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        graph[i].clear();
        weak[i].clear();
        indeg[i] = outdeg[i] = iter_[i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        weak[u].push_back(v);
        weak[v].push_back(u);
        outdeg[u]++;
        indeg[v]++;
    }

    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    if (!check_connected()) {
        cout << "No\n";
        return 0;
    }

    int start = find_start();
    if (start == -1) {
        cout << "No\n";
        return 0;
    }

    path.clear();
    hierholzer(start);

    if ((int) path.size() != m + 1) {
        cout << "No\n";
        return 0;
    }

    for (int i = m; i >= 0; i--) {
        cout << path[i];
        if (i > 0) {
            cout << ' ';
        }
    }
    cout << '\n';

    return 0;
}

复杂度

设点数为 n，边数为 m。

判连通和度数检查是 $O(n + m)$
邻接表排序总复杂度 $O(m \log m)$ 量级
Hierholzer 主过程是 $O(n + m)$

总时间复杂度 $O(m \log m)$ ，空间复杂度 $O(n + m)$ 。

总结

这题就是“有向欧拉路 + 字典序”模板。难点不在 Hierholzer 本身，而在两件事：

先把欧拉路存在条件判对
再利用“答案逆序产生”这个性质，把出边顺序处理成最终的最小字典序

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P7771 【模板】欧拉路径

题目描述

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

输入格式

第一行两个整数 $n,m$ 表示有向图的点数和边数。

接下来 $m$ 行每行两个整数 $u,v$ 表示存在一条 $u\to v$ 的有向边。

输出格式

如果不存在欧拉路径，输出一行 No。

否则输出一行 $m+1$ 个数字，表示字典序最小的欧拉路径。

输入输出样例 #1

输入 #1

text

输出 #1

text

11 2 1 3 3 4 2

输入输出样例 #2

输入 #2

text

输出 #2

text

11 2 3 4 3 5

输入输出样例 #3

输入 #3

text

输出 #3

text

1No

说明/提示

对于 $50\%$ 的数据， $n,m\leq 10^3$ 。

对于 $100\%$ 的数据， $1\leq u,v\leq n\leq 10^5$ ， $m\leq 2\times 10^5$ 。

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

本题的数据生成器：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
typedef unsigned long long ull;
#define N 100005
#define For(i,x,y)for(i=x;i<=(y);i++)
bool bo[N];
queue<int>p,q;
ull R=GetTickCount();
int deg[N][2],dep[N],fa[N];
inline int Rand(int _,int __)
{
	R^=R<<13;
	R^=R>>7;
	R^=R<<17;
	return R%(__-_+1)+_;
}
int find(int p)
{
	if(p!=fa[p])fa[p]=find(fa[p]);
	return fa[p];
}
inline void unite(int p,int q)
{
	p=find(p),q=find(q);
	if(p==q)return;
	if(dep[p]<dep[q])fa[p]=q;
	else fa[q]=p;
	if(dep[p]==dep[q])dep[p]++;
}
int main()
{
	freopen("P7771.in","w",stdout);
	int n=Rand(1,100000),m=Rand(190000,200000),i,u,v;
	cout<<n<<' '<<m;
	For(i,1,n)fa[i]=i;
	For(i,1,m>>1)
	{
		u=Rand(1,n),v=Rand(1,n);
		cout<<endl<<u<<' '<<v;
		unite(u,v);
		deg[u][0]++;
		deg[v][1]++;
	}
	m-=m>>1;
	For(i,1,n)
	if(deg[i][0]<deg[i][1])p.push(i);
	else if(deg[i][0]>deg[i][1])q.push(i);
	while(m)
	{
		if(p.empty()||q.empty())break;
		u=p.front();
		v=q.front();
		p.pop();
		q.pop();
		unite(u,v);
		cout<<endl<<u<<' '<<v;
		deg[u][0]++;
		deg[v][1]++;
		if(deg[u][0]<deg[u][1])p.push(u);
		if(deg[v][0]>deg[v][1])q.push(v);
		m--;
	}
	For(i,1,n-1)
	if(find(i)!=find(n))
	{
		cout<<endl<<n<<' '<<i<<endl<<i<<' '<<n;
		m-=2;
		unite(n,i);
	}
	if(m<2)
	while(1);
	while(m>Rand(0,1))
	{
		u=Rand(1,n);
		cout<<endl<<u<<' '<<u;
		m--;
	}
	if(m)cout<<endl<<Rand(1,n)<<' '<<Rand(1,n);
	return 0;
}

【模板】欧拉路径

目录

题意

样例图

思路

代码

复杂度

总结

一图流解析