【ACM算法竞赛】欧拉路径/欧拉回路算法模板和题目详解

2401_88501775

832人浏览 · 2026-05-13 17:28:54

2401_88501775 · 2026-05-13 17:28:54 发布

在这里插入图片描述

1.引言

欧拉路径的算法可以解决图的“一笔画”问题，一笔画问题指在平面上用连续的、不重复的线条绘制一个图形，且笔不离开纸面。在最简单的模板套用之外，还可以用于解决”构造恰好用干净某类资源的方案“等问题，这也在后面的题目里有所涉及。另外也有题目套用一个欧拉路径的存在条件的壳，考察其他知识点。
求欧拉回路的完整模板代码在第5部分。

2.欧拉路径/回路的定义

欧拉路径：是指在图论中，经过图中每一条边且每一条边仅经过一次的路径。
欧拉回路：起点和终点是同一个顶点的欧拉路径，成为欧拉回路。
欧拉回路是特殊的欧拉路径，多一个首尾相同的要求（回路一定要是回路QwQ）。

3.欧拉路径/回路存在的条件

对于无向图：
- 存在欧拉路径的条件是恰好有0个或2个点的度数为奇数，并且图是连通的。
- 存在欧拉回路的条件是恰好有0个点的度数为奇数，并且图是连通的。
- PS: 如果恰有2个点度数为奇数则不存在欧拉回路，只存在欧拉路径，并且该条欧拉路径的起点和终点就是那两个度数为奇数的点。
对于有向图：
- 存在欧拉路径的条件：所有顶点的入度等于出度，或者恰好有一个顶点的出度比入度大1（作为起点），另一个顶点的入度比出度大1（作为终点），并且图是弱连通的。
- 存在欧拉回路的条件：如果所有顶点的入度等于出度，并且图是弱连通的。

上述条件可以简要归纳为”点的度数条件“和”图的连通条件“。

4.欧拉路径/回路的求法。

最常用的求法是 Hierholzer 算法。
算法的具体流程为先从图中找到一条回路作为当前回路，每次从当前回路中选取剩余度数不为零的点，从该点出发找到一条新的简单回路，并将该简单回路与当前回路合并，重复该过程直到当前回路中的所有点均无剩余度数，此时的当前回路即为欧拉回路。
传送门：更严谨复杂的数学证明（oiwiki）

5.算法模板

实际使用的时候，存在两个维度的四种不同需求：
- 只保留欧拉路径经过的点的序列，而不管经过的边。还是经过的边的编号也要保留？
- 是无向图还是有向图?
所以直接给出4个算法模板，虽然第1个就能解决80%的情况，也足够通过模板题了，但后面的复杂模板也是被使用过的。

5.1有向图+只保留点

最简单的一版，加个存在性判断就够过模板题，解决大多数情况。
存在性判断在后面的版本里有，自己手动写也很好，存在的条件已经讲过了(在第三部分）。

void Hierholzer_easy_directed(){
	int n;
	vector<vector<int>> v(n + 1);   // 只存有向出边
	vector<int> p(n + 1);           // 当前点扫到第几条出边
	vector<int> path;               
	
	auto dfs = [&](auto &&self, int u) -> void {
		while (p[u] < v[u].size()) {
			int ne = v[u][p[u]++];
			self(self, ne);
		}
		path.push_back(u);     
	};
	int st; 
	dfs(dfs, st);
	reverse(path.begin(), path.end()); 
	//path里就是点序列最终的点序列
}

5.2无向图+只保留点

对于无向图，我们通过给边编号的方法，保证每一个无向边只被使用一次，用过了把这个编号禁掉就可以。
当然专业的说法是设置“半边”，把一条无向边拆成共享同一个 $i d$ 的两条有向边，这两条有向边被称作原无向边的“半边”，经过任意一条半边就禁用编号。

void Hierholzer_easy_undirected() {
	int n, m;
	cin >> n >> m;
	
	// 邻接表存 {邻居, 边编号}
	vector<vector<pair<int, int>>> v(n + 1);
	vector<int> used(m + 1, 0);   // 标记边是否被用过
	int eid = 0;
	
	// 加边函数：无向边 = 两条有向边，共用同一个 eid
	auto add_edge = [&](int l, int r) {
		v[l].push_back({r, eid});
		v[r].push_back({l, eid});
		eid++;
	};
	
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		add_edge(x, y);
	}
	
	vector<int> p(n + 1, 0);   // 每个点走到第几条邻接边
	vector<int> path;
	
	auto dfs = [&](auto &&self, int u) -> void {
		while (p[u] < (int)v[u].size()) {
			auto [ne, id] = v[u][p[u]++];
			if (used[id]) continue;   // 反向边已被走过
			used[id] = 1;             // 标记这条无向边已用
			self(self, ne);
		}
		path.push_back(u);
	};
	
	int st = 1;   // 若题目没给起点，就选第一个有边的点
	dfs(dfs, st);
	reverse(path.begin(), path.end());
	
	for (int x : path) cout << x << ' ';
	cout << '\n';
}

5.3 判断有无解+有向图+保留点和边

给每条边分一个编号，同时记录每条边的起点终点，后面找回路的时候同时记录点和入边的编号，再还原就行了。
加边操作有点复杂了，封装成addedge函数了。


void Hierholzer_directed() {
	int n, m;
	cin >> n >> m;
	
	vector<vector<PII>> v(n + 1); // 只存有向边：v[u] = {to, eid}
	vector<vector<int>> ug(n + 1); // 忽略方向后的图，只给 check 用
	vector<int> from, to;
	vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
	int eid = 0;
	
	auto addedge = [&](int l, int r) -> int {
		v[l].push_back({r, eid});
		ug[l].push_back(r);
		ug[r].push_back(l);
		from.push_back(l);
		to.push_back(r);
		outdeg[l]++;
		indeg[r]++;
		return eid++;
	};
	
	for (int i = 1; i <= m; i++) {
		int u, vtx;
		cin >> u >> vtx;
		addedge(u, vtx);
	}
	
	auto check = [&]() -> pair<int,int> {
		vector<int> vis(n + 1, 0);
		int st = -1;
		int s1 = -1, s2 = -1; // s1: out-in = 1, s2: in-out = 1
		
		for (int i = 1; i <= n; i++) {
			if (indeg[i] + outdeg[i] && st == -1) st = i;
			
			if (outdeg[i] - indeg[i] == 1) {
				if (s1 != -1) return {0, -1};
				s1 = i;
			} else if (indeg[i] - outdeg[i] == 1) {
				if (s2 != -1) return {0, -1};
				s2 = i;
			} else if (indeg[i] != outdeg[i]) {
				return {0, -1};
			}
		}
		
		// 连通性：忽略方向后必须连通
		int cnt = 0;
		auto dfs = [&](auto &&self, int u) -> void {
			vis[u] = 1;
			cnt ++;
			for (int r : ug[u]) {
				if (!vis[r]) self(self, r);
			}
		};
		
		dfs(dfs, st);
		
		if (cnt < n) return {0, -1};
		if (s1 == -1 && s2 == -1) return {2, st};
		if (s1 != -1 && s2 != -1) return {1, s1};
		
		return {0, -1};
	};
	
	auto [type, st] = check();
	if (type == 0) {
		cout << "No\n";
		return;
	}
	
	vector<int> p(n + 1), edge, node;
	
	auto dfs = [&](auto &&self, int u, int peid) -> void {
		while (p[u] < (int)v[u].size()) {
			auto [r, id] = v[u][p[u]++];
			self(self, r, id);
		}
		edge.push_back(peid);
		node.push_back(u);
	};
	
	dfs(dfs, st, -1);
	reverse(edge.begin(), edge.end());
	reverse(node.begin(), node.end());
	
	// node: 点序列
	// edge: 边序列，edge[0] = -1
	for (int x : node) cout << x << ' ';
	cout << '\n';
}

5.4.无向图+保留点和边

void Hierholzer_undirected() {
	int n, m;
	cin >> n >> m;
	
	vector<vector<PII>> v(n + 1); // v[u] = {to, eid}
	vector<int> from, to, used, deg(n + 1, 0);
	int eid = 0;
	
	auto addedge = [&](int l, int r) -> int {
		v[l].push_back({r, eid});
		v[r].push_back({l, eid});
		from.push_back(l);
		to.push_back(r);
		used.push_back(0);
		deg[l]++;deg[r]++;
		return eid++;
	};
	
	for (int i = 1; i <= m; i++) {
		int x,y;
		cin >> x >> y;
		addedge(x, y);
	}
	
	auto check = [&]() -> pair<int,int> {
		vector<int> odd, vis(n + 1, 0);
		int st = -1;
		
		for (int i = 1; i <= n; i++) {
			if (deg[i] && st == -1) st = i;
			if (deg[i] & 1) odd.push_back(i);
		}
		
		// 无向图欧拉路径条件：奇度点个数只能是 0 或 2
		if (!(odd.size() == 0 || odd.size() == 2)) return {0, -1};
		
		int cnt = 0;
		auto dfs = [&](auto &&self, int u) -> void {
			vis[u] = 1;
			cnt ++;
			for (auto [r, id] : v[u]) {
				if (!vis[r]) self(self, r);
			}
		};
		
		dfs(dfs, st);

		if (cnt < n) return {0, -1};         // 不存在
		if (odd.size() == 0) return {2, st};  // 欧拉回路
		return {1, odd[0]};                   // 欧拉路径
	};
	
	auto [type, st] = check();
	if (type == 0) {
		cout << "No\n";
		return;
	}
	
	vector<int> p(n + 1), edge, node;
	
	auto dfs = [&](auto &&self, int u, int peid) -> void {
		while (p[u] < (int)v[u].size()) {
			auto [r, id] = v[u][p[u]++];
			if (used[id]) continue;
			used[id] = 1;
			self(self, r, id);
		}
		edge.push_back(peid);
		node.push_back(u);
	};
	
	dfs(dfs, st, -1);
	reverse(edge.begin(), edge.end());
	reverse(node.begin(), node.end());
	
	// node: 点序列
	// edge: 边序列，edge[0] = -1
	for (int x : node) cout << x << ' ';
	cout << '\n';
}

5.5.四合一大礼包

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;

void Hierholzer_easy_undirected() {
	int n, m;
	cin >> n >> m;
	
	// 邻接表存 {邻居, 边编号}
	vector<vector<pair<int, int>>> v(n + 1);
	vector<int> used(m + 1, 0);   // 标记边是否被用过
	int eid = 0;
	
	// 加边函数：无向边 = 两条有向边，共用同一个 eid
	auto add_edge = [&](int l, int r) {
		v[l].push_back({r, eid});
		v[r].push_back({l, eid});
		eid++;
	};
	
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		add_edge(x, y);
	}
	
	vector<int> p(n + 1, 0);   // 每个点走到第几条邻接边
	vector<int> path;
	
	auto dfs = [&](auto &&self, int u) -> void {
		while (p[u] < (int)v[u].size()) {
			auto [ne, id] = v[u][p[u]++];
			if (used[id]) continue;   // 反向边已被走过
			used[id] = 1;             // 标记这条无向边已用
			self(self, ne);
		}
		path.push_back(u);
	};
	
	int st = 1;   // 若题目没给起点，就选第一个有边的点
	dfs(dfs, st);
	reverse(path.begin(), path.end());
	
	for (int x : path) cout << x << ' ';
	cout << '\n';
}

void Hierholzer_easy_directed(){
	int n;
	vector<vector<int>> v(n + 1);   // 只存有向出边
	vector<int> p(n + 1);           // 当前点扫到第几条出边
	vector<int> path;               
	
	auto dfs = [&](auto &&self, int u) -> void {
		while (p[u] < v[u].size()) {
			int ne = v[u][p[u]++];
			self(self, ne);
		}
		path.push_back(u);     
	};
	int st; 
	dfs(dfs, st);
	reverse(path.begin(), path.end());
}

void Hierholzer_undirected() {
	int n, m;
	cin >> n >> m;
	
	vector<vector<PII>> v(n + 1); // v[u] = {to, eid}
	vector<int> from, to, used, deg(n + 1, 0);
	int eid = 0;
	
	auto addedge = [&](int l, int r) -> int {
		v[l].push_back({r, eid});
		v[r].push_back({l, eid});
		from.push_back(l);
		to.push_back(r);
		used.push_back(0);
		deg[l]++;deg[r]++;
		return eid++;
	};
	
	for (int i = 1; i <= m; i++) {
		int x,y;
		cin >> x >> y;
		addedge(x, y);
	}
	
	auto check = [&]() -> pair<int,int> {
		vector<int> odd, vis(n + 1, 0);
		int st = -1;
		
		for (int i = 1; i <= n; i++) {
			if (deg[i] && st == -1) st = i;
			if (deg[i] & 1) odd.push_back(i);
		}
		
		// 无向图欧拉路径条件：奇度点个数只能是 0 或 2
		if (!(odd.size() == 0 || odd.size() == 2)) return {0, -1};
		
		int cnt = 0;
		auto dfs = [&](auto &&self, int u) -> void {
			vis[u] = 1;
			cnt ++;
			for (auto [r, id] : v[u]) {
				if (!vis[r]) self(self, r);
			}
		};
		
		dfs(dfs, st);

		if (cnt < n) return {0, -1};         // 不存在
		if (odd.size() == 0) return {2, st};  // 欧拉回路
		return {1, odd[0]};                   // 欧拉路径
	};
	
	auto [type, st] = check();
	if (type == 0) {
		cout << "No\n";
		return;
	}
	
	vector<int> p(n + 1), edge, node;
	
	auto dfs = [&](auto &&self, int u, int peid) -> void {
		while (p[u] < (int)v[u].size()) {
			auto [r, id] = v[u][p[u]++];
			if (used[id]) continue;
			used[id] = 1;
			self(self, r, id);
		}
		edge.push_back(peid);
		node.push_back(u);
	};
	
	dfs(dfs, st, -1);
	reverse(edge.begin(), edge.end());
	reverse(node.begin(), node.end());
	
	// node: 点序列
	// edge: 边序列，edge[0] = -1
	for (int x : node) cout << x << ' ';
	cout << '\n';
}

void Hierholzer_directed() {
	int n, m;
	cin >> n >> m;
	
	vector<vector<PII>> v(n + 1); // 只存有向边：v[u] = {to, eid}
	vector<vector<int>> ug(n + 1); // 忽略方向后的图，只给 check 用
	vector<int> from, to;
	vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
	int eid = 0;
	
	auto addedge = [&](int l, int r) -> int {
		v[l].push_back({r, eid});
		ug[l].push_back(r);
		ug[r].push_back(l);
		from.push_back(l);
		to.push_back(r);
		outdeg[l]++;
		indeg[r]++;
		return eid++;
	};
	
	for (int i = 1; i <= m; i++) {
		int u, vtx;
		cin >> u >> vtx;
		addedge(u, vtx);
	}
	
	auto check = [&]() -> pair<int,int> {
		vector<int> vis(n + 1, 0);
		int st = -1;
		int s1 = -1, s2 = -1; // s1: out-in = 1, s2: in-out = 1
		
		for (int i = 1; i <= n; i++) {
			if (indeg[i] + outdeg[i] && st == -1) st = i;
			
			if (outdeg[i] - indeg[i] == 1) {
				if (s1 != -1) return {0, -1};
				s1 = i;
			} else if (indeg[i] - outdeg[i] == 1) {
				if (s2 != -1) return {0, -1};
				s2 = i;
			} else if (indeg[i] != outdeg[i]) {
				return {0, -1};
			}
		}
		
		// 连通性：忽略方向后必须连通
		int cnt = 0;
		auto dfs = [&](auto &&self, int u) -> void {
			vis[u] = 1;
			cnt ++;
			for (int r : ug[u]) {
				if (!vis[r]) self(self, r);
			}
		};
		
		dfs(dfs, st);
		
		if (cnt < n) return {0, -1};
		if (s1 == -1 && s2 == -1) return {2, st};
		if (s1 != -1 && s2 != -1) return {1, s1};
		
		return {0, -1};
	};
	
	auto [type, st] = check();
	if (type == 0) {
		cout << "No\n";
		return;
	}
	
	vector<int> p(n + 1), edge, node;
	
	auto dfs = [&](auto &&self, int u, int peid) -> void {
		while (p[u] < (int)v[u].size()) {
			auto [r, id] = v[u][p[u]++];
			self(self, r, id);
		}
		edge.push_back(peid);
		node.push_back(u);
	};
	
	dfs(dfs, st, -1);
	reverse(edge.begin(), edge.end());
	reverse(node.begin(), node.end());
	
	// node: 点序列
	// edge: 边序列，edge[0] = -1
	for (int x : node) cout << x << ' ';
	cout << '\n';
}

6.模板题 P7771 【模板】欧拉路径

【原题链接，点我传送】

题目描述

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

输入格式

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

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

输出格式

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

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

输入输出样例 #1

输入 #1

输出 #1

1 2 1 3 3 4 2

输入输出样例 #2

输入 #2

输出 #2

1 2 3 4 3 5

输入输出样例 #3

输入 #3

输出 #3

No

说明/提示

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

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

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

解题思路

模板题，对边排序之后用模板就可以了。

AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;

void solve() {
	int n, m;
	cin >> n >> m;
	
	vector<vector<PII>> v(n + 1); // 只存有向边：v[u] = {to, eid}
	vector<vector<int>> ug(n + 1); // 忽略方向后的图，只给 check 用
	vector<int> from, to;
	vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
	int eid = 0;
	
	auto addedge = [&](int l, int r) -> int {
		v[l].push_back({r, eid});
		ug[l].push_back(r);
		ug[r].push_back(l);
		from.push_back(l);
		to.push_back(r);
		outdeg[l]++;
		indeg[r]++;
		return eid++;
	};
	vector<vector<int>> tmpv(n+1);
	
	
	for(int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		tmpv[x].push_back(y);
	}
	
	for(int i = 1; i <= n; i ++){
		sort(tmpv[i].begin(),tmpv[i].end());
		for(int j : tmpv[i]){
			addedge(i,j);
		}
	}
	
	auto check = [&]() -> pair<int,int> {
		vector<int> vis(n + 1, 0);
		int st = -1;
		int s1 = -1, s2 = -1; // s1: out-in = 1, s2: in-out = 1
		
		for (int i = 1; i <= n; i++) {
			if (indeg[i] + outdeg[i] && st == -1) st = i;
			
			if (outdeg[i] - indeg[i] == 1) {
				if (s1 != -1) return {0, -1};
				s1 = i;
			} else if (indeg[i] - outdeg[i] == 1) {
				if (s2 != -1) return {0, -1};
				s2 = i;
			} else if (indeg[i] != outdeg[i]) {
				return {0, -1};
			}
		}
		
		// 连通性：忽略方向后必须连通
		int cnt = 0;
		auto dfs = [&](auto &&self, int u) -> void {
			vis[u] = 1;
			cnt ++;
			for (int r : ug[u]) {
				if (!vis[r]) self(self, r);
			}
		};
		
		dfs(dfs, st);
		
		if (cnt < n) return {0, -1};
		if (s1 == -1 && s2 == -1) return {2, st};
		if (s1 != -1 && s2 != -1) return {1, s1};
		
		return {0, -1};
	};
	
	auto [type, st] = check();
	if (type == 0) {
		cout << "No\n";
		return;
	}
	
	vector<int> p(n + 1), edge, node;
	
	auto dfs = [&](auto &&self, int u, int peid) -> void {
		while (p[u] < (int)v[u].size()) {
			auto [r, id] = v[u][p[u]++];
			self(self, r, id);
		}
		edge.push_back(peid);
		node.push_back(u);
	};
	
	dfs(dfs, st, -1);
	reverse(edge.begin(), edge.end());
	reverse(node.begin(), node.end());
	
	// node: 点序列
	// edge: 边序列，edge[0] = -1
	for (int x : node) cout << x << ' ';
	cout << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	//cin >> t;
	while(t --){
		solve();
	}
}

7.高阶应用

非战斗人员可以尽快撤离。

7.1 Swap to Rearrange

题目传送门：Codeforces Round 1081 (Div. 2) E. Swap to Rearrange

对于 1 ~ n 的每个数字，其分给 $a$ 数组的数量和不分给 $a$ 数组必须相同。如果把每个自然数看作一个点，这个结论可翻译为每个点的入度和出度相同。
欧拉回路中，每个点的入度和出度相同。
考虑在每一对 $a [i], b [i]$ 之间建立一条无向边，找到一条合法的欧拉回路即可。
无向图找欧拉回路的方法：将一条无向边拆为两条共享同一个 $i d$ 的有向边，称这两条有向边又称为无向边的“半边”。找欧拉回路时，经过一条有向边就标记其 $i d$ 为已使用，确保每条无向边只走过一次。

#include<bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int,int> PII;

struct edge{
	int x,id,dir;
	edge(int _x,int _id,int _dir):x(_x),id(_id),dir(_dir){}
};

void solve(){
	int n;
	cin >> n;
	vector<int> a(n+1),b(n+1);
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	for(int i = 1; i <= n; i ++){
		cin >> b[i];
	}

	vector<int> p(n+1),deg(n+1);
	
	
	vector<int> done(n+1);
	vector<vector<edge>> v(n+1);
	//0 a->b 
	for(int i = 1; i <= n; i ++){
		v[a[i]].emplace_back(b[i],i,1);
		v[b[i]].emplace_back(a[i],i,0);
		deg[a[i]] ++,deg[b[i]] ++;
	}

	for(int i = 1; i <= n; i ++){
		if(deg[i] % 2 != 0){
			cout << -1 << '\n';
			return;
		}
	}
	vector<int> ans,vis(n+1);

	auto dfs = [&](auto &&self,int u)->void{
		vis[u] = 1;
		while(p[u] < v[u].size()){
			auto [i,id,dir] = v[u][p[u] ++];
			if(done[id]) continue;
			done[id] = 1;
			if(dir) ans.push_back(id);
			
			self(self,i);
		}
	};

	for(int i = 1; i <= n; i ++){
		if(!vis[i]){
			dfs(dfs,i);
			
		}
	}
	
	cout << ans.size() << '\n';
	for(int i : ans){
		cout << i << ' ';
	}
	cout << '\n';
	
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
}

7.2. Zhily and Cycle

题目传送门：Codeforces Round 1097 (Div. 1, Based on Zhili Cup 2026) D. Zhily and Cycle

肯定要转成欧拉回路求解，不然炸复杂度了，我们把每个点的出边 $i，a_u)$ 转化成 $i，a_i)，(a_i,a_u)$ 两条边，找到新图的一个欧拉回路，再删掉第二条边就得到哈密顿回路。
先把每个 $i$ 连上第一部分的边 $i ， a_i)$ 。
如果对于每一个当前入度出度不平衡的点，恰好能找到n条边使得整个图入度出度平衡就有解了。
观察所有入度大于出度的点，假设差值为 $d e g$ ，它们恰好能连 $d e g$ 条边，每条边能且只能连向序号大于它的点。因为他们入度大于出度本身是由 $i，a_i)$ 导致的，后面必定要跟一条(a_i,a_u)，(a_i,a_u)这条边的要求有且仅有下一个点的序号更大。
我们把(a_i,a_u)称作前向边，贪心解决这个问题。
定义 $d e g [i]$ 为点 $i$ 的入度和出度的差值。对 $d e g$ 求前缀和 $p er$ ，一旦出现 $p r e [i] < 0$ 则无解。每一个 $p r e [i] == 0$ 的位置成为切分点，因为不能有前向边跨过 $p r e [i] == 0$ 的位置，一旦跨过 $p r e [i]$ 减为负。
对于两个 $p r e [i] == 0$ 所夹的区间，先贪心地连 $(i ， i + 1)$ ，最后一个位置不加边，保证块内联通，然后把 $d e g [i] > 0$ 的点记下来,作为提供者，遇到 $d e g [i] < 0$ 就连一条提供者到该点的前向边。
如果新图不连通输出"No"。
用模板求新图的欧拉回路。只保留欧拉回路中 $i，a_i)$ 这类边的左端点，就得到了答案。

#include<bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int,int> PII;

void solve(){
	int n;
	cin >> n;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	vector<vector<int>> v(n+1);
	struct edge{
		int l,r,fix;
	};
	vector<edge> e;
	int np = 0;
	vector<int> deg(n+1);
	auto addedge = [&](int l,int r,int fix)->void{
		deg[l] --;
		deg[r] ++;
		e.push_back({l,r,fix});
		v[l].push_back(np);
		np ++; 
	};
	

	for(int i = 1; i <= n; i ++){
		addedge(i,a[i],1);
	}
	vector<int> pre(n+1);
	int last = 1;
	auto work = [&](int l,int r)->void{
		for(int i = l; i <= r - 1; i ++){
			addedge(i,i+1,0);
		}
	
		vector<PII> stk;
		for(int i = l; i <= r; i ++){
			if(deg[i] > 0){
				stk.push_back({i,deg[i]});
			}
			else if(deg[i] < 0){
				while(deg[i] < 0){
					addedge(stk.back().first,i,0);
					stk.back().second --;
					if(!stk.back().second) stk.pop_back();
				}
			}
		}
	};
	
	for(int i = 1; i <= n ; i ++){
		pre[i] = pre[i-1] + deg[i];
		if(pre[i] < 0){
			cout << "No\n";
			return;
		}
		if(pre[i] == 0){
			work(last,i);
			last = i + 1;
		}
	}
	
	vector<int> done(n+1);
	int cnt = 0;
	auto dfs = [&](auto &&self,int u)->void{
		done[u] = 1;
		cnt ++;
		for(int i : v[u]){
			if(!done[e[i].r]){
				self(self,e[i].r);
			}
		}
	};
	dfs(dfs,1);
	if(cnt != n){
		cout << "No\n";
		return;
	}
	
	vector<int> p(n+1);
	vector<int> euler;
	auto dfs2 = [&](auto &&self,int u,int id)->void{
		while(p[u] < v[u].size()){
			int eid = v[u][p[u]++];
			self(self,e[eid].r,eid);
		}
		euler.push_back(id);
	};
	dfs2(dfs2,1,-1);
	reverse(euler.begin(),euler.end());
	vector<int> ans;
	for(auto i : euler){
		if(i != -1 && e[i].fix){
			ans.push_back(e[i].l);
		}
	}
	cout << "Yes\n";
	for(int i : ans){
		cout << i << ' ';
	}
	cout << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
}

7.3 Eulerian Flight Tour

题目传送门：2018-2019, ICPC, Asia Yokohama Regional Contest 2018 E - Eulerian Flight Tour

欧拉路径的两条特性：1.连通，2，边的度数为偶数。
我们只关心度数的奇偶性，偶数看成0，奇数看成1。
加一条边的实质是对边的两个端点的度数做一次异或运算。
把每条边看成未知数，对每个点列一个方程组。用bitset优化高斯消元解异或方程组，得到一个特解，满足所有边度数为偶数。
问题是 0 也算偶数，原图可能不连通，需要构造补边保证连通性。
下面解决连通性：
- 有三个以上连通块，则每个连通块挑一个点，这些点首尾相邻即可。
- 两个连通块：
  - 若两个块都至少两个点，各条两个点，让它们和另一个块的两个点相连，形似K（2，2）。
  - 若有一个点为单点：
    - 另一个块有新加的边，可以把这个点插到这条新加边的中间。
    - 另一个块有两个不直接相连的点，把这俩个点和单点连一个三角形。
    - 都不满足就无解。
  - 两个点均单点，无解。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;

const int N = 5001,M = 101;

struct Gauss {
	int n, m;
	bitset<N> a[M];
	vector<int> where;
	
	Gauss(int n, int m, bitset<N> matrix[]) :n(n),m(m),where(n+1,-1){
		for (int i = 1; i <= m; i++) a[i] = matrix[i];
	}
	
	void elimination() {
		int row = 1;
		for (int col = 1; col <= n && row <= m; col++) {
			int sel = row;
			
			while (sel <= m && !a[sel][col]) sel++;
			if (sel > m) continue; // 自由变量
			
			swap(a[sel], a[row]);
			where[col] = row;
			
			for (int i = 1; i <= m; i++) {
				if (i != row && a[i][col]) {
					a[i] ^= a[row];
				}
			}
			row++;
		}
	}
	
	// 无解返回 {}
	// 有解返回答案，自由变量为 -1
	vector<int> work() {
		elimination();
		// 判断无解：0 = 1
		for (int i = 1; i <= m; i++) {
			bool all0 = true;
			for (int j = 1; j <= n; j++) {
				if (a[i][j]) {
					all0 = false;
					break;
				}
			}
			if (all0 && a[i][0]) return {};
		}
		
		vector<int> ans(n + 1);
		
		for (int i = 1; i <= n; i++) {
			if (where[i] != -1) {
				ans[i] = a[where[i]][0];
			}else{
				//自由变量全设为0，得到一组特解。
				ans[i] = 0;
			}
		}
		
		return ans;
	}
};

struct Dsu{
	int n;
	vector<int> f,siz;
	
	Dsu(int _n):n(_n),f(n+1){
		iota(f.begin()+1,f.end(),1);
		siz.assign(n+1,1);
	}
	
	int find(int x){
		if(f[x] != x) f[x] = find(f[x]);
		return f[x];
	}
	
	void merge(int x,int y){
		x = find(x),y = find(y);
		if(x != y){
			siz[x] += siz[y];
			f[y] = x;
		}
	}
};

void solve(){
	int n,m;
	cin >> n >> m;
	bitset<N> b[M];
	Dsu dsu(n+1);
	vector<vector<int>> v(n+1,vector<int>(n+1));
	for(int i = 1; i <= m; i ++){
		int x,y;
		cin >> x >> y;
		v[x][y] = 1,v[y][x] = 1;
		dsu.merge(x,y);
	}
	map<PII,int> mp;
	vector<pair<int,int>> edge(n*n + 10);
	int p = 1;
	for(int i = 1; i <= n; i ++){
		for(int j = i + 1; j <= n; j ++){
			if(!v[i][j]){
				mp[{i,j}] = p;
				mp[{j,i}] = p;
				edge[p] = {i,j};
				p ++;
			}
		}
	}
	p --;
	for(int i = 1; i <= n; i ++){
		int cnt = 0;
		for(int j = 1; j <= n; j ++){
			if(i == j) continue;
			if(!v[i][j]){
				int idx = mp[{i,j}];
				b[i][idx] = 1;
			}
			else cnt ^= 1;
		}
		//cout << cnt << '\n';
		b[i][0] = cnt;
		//cout << b[i][0] << '\n';
	}
	
	Gauss gauss(p,n,b);
	vector<int> ans = gauss.work();
	if(ans.empty()){
		cout << -1 << '\n';
		return;
	}else{
		for(int i = 1; i <= p; i ++){
			if(ans[i]){
				auto [x,y] = edge[i];
				v[x][y] = 2;
				v[y][x] = 2;
				dsu.merge(x,y);
			}
		}
	}
	
	
	vector<PII> ret;
	/*
	for(int i = 1; i <= n; i ++){
		for(int j = i + 1; j <= n; j ++){
			if(v[i][j] == 2){
				ret.push_back({i,j});
			}
		}
	}
	cout << ret.size() << '\n';
	for(auto [x,y] : ret){
		cout << x << ' ' << y << '\n';
	}
	*/
	map<int,int> num;
	for(int i = 1; i <= n; i ++){
		num[dsu.find(i)] ++;
	}
	
	
	if(num.size() == 1){
		//
	}else if(num.size() == 2){
		if(num.begin()->second >= 2 && num.rbegin()->second >= 2){
			int aa = -1,b = -1,c = -1,d = -1;
			for(int i = 1; i <= n; i ++){
				if(dsu.find(i) == num.begin()->first){
					if(aa == -1) aa = i;
					else b = i;
				}else{
					if(c == -1) c = i;
					else d = i;
				}
			}
			v[aa][c] = v[c][aa] = 2;
			v[aa][d] = v[d][aa] = 2;
			
			v[b][c] = v[c][b] = 2;
			v[b][d] = v[d][b] = 2;
		}else if(num.begin()->second == 1){
			int aa = -1,b = -1,c = -1;
			for(int i = 1; i <= n; i ++){
				if(dsu.find(i) == num.begin()->first){
					aa = i;
					break;
				}
			}
			for(int i = 1; i <= n; i ++){
				for(int j = 1; j <= n; j ++){
					if(i == aa || j == aa || i == j) continue;
					if(v[i][j] == 2){
						b = i,c = j;
						break;
					}
				}
				if(b != -1) break;
			}
			if(b == -1){
				for(int i = 1; i <= n; i ++){
					for(int j = 1; j <= n; j ++){
						if(i == aa || j == aa || i == j) continue;
						if(v[i][j] == 0){
							b = i,c = j;
							break;
						}
					}
					if(b != -1) break;
				}
				if(b == -1){
					cout << -1 << '\n';
					return;
				}
				v[b][c] = v[c][b] = 2;	
				v[aa][b]= v[b][aa] = 2;
				v[aa][c] = v[c][aa] = 2;
			}
			else{
				v[b][c] = v[c][b] = 0;	
				v[aa][b]= v[b][aa] = 2;
				v[aa][c] = v[c][aa] = 2;
			}
		}
		else if(num.rbegin()->second == 1){
			int aa = -1,b = -1,c = -1;
			for(int i = 1; i <= n; i ++){
				if(dsu.find(i) == num.rbegin()->first){
					aa = i;
					break;
				}
			}
			for(int i = 1; i <= n; i ++){
				for(int j = 1; j <= n; j ++){
					if(i == aa || j == aa || i == j) continue;
					if(v[i][j] == 2){
						b = i,c = j;
						break;
					}
				}
				if(b != -1) break;
			}
			if(b == -1){
				for(int i = 1; i <= n; i ++){
					for(int j = 1; j <= n; j ++){
						if(i == aa || j == aa || i == j) continue;
						if(v[i][j] == 0){
							b = i,c = j;
							break;
						}
					}
					if(b != -1) break;
				}
				if(b == -1){
					cout << -1 << '\n';
					return;
				}
				v[b][c] = v[c][b] = 2;	
				v[aa][b]= v[b][aa] = 2;
				v[aa][c] = v[c][aa] = 2;
			}
			else{
				v[b][c] = v[c][b] = 0;	
				v[aa][b]= v[b][aa] = 2;
				v[aa][c] = v[c][aa] = 2;
			}
		}else{
			cout << -1 << '\n';
			return;
		}
			
	}else{
		set<int> s;
		vector<int> q;
		for(int i = 1; i <= n; i ++){
			int id = dsu.find(i);
			if(s.find(id) == s.end()){
				s.insert(id);
				q.push_back(i);
			} 
		}
		
		for(int i = 1; i < q.size(); i ++){
			v[q[i-1]][q[i]] = 2;
			v[q[i]][q[i-1]] = 2;
		}
		v[q[0]][q.back()] = 2;
		v[q.back()][q[0]] = 2;
	}
	
	//vector<PII> ret;
	//ret.clear();
	for(int i = 1; i <= n; i ++){
		for(int j = i + 1; j <= n; j ++){
			if(v[i][j] == 2){
				ret.push_back({i,j});
			}
		}
	}
	cout << ret.size() << '\n';
	for(auto [x,y] : ret){
		cout << x << ' ' << y << '\n';
	}
	
	
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int T = 1;
	//cin >> T;
	while(T--) solve();
	return 0;
}

openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

ArXiv cs.AI 每日论文精选 | 2026-09-19

openEuler 社区

PHP 程序员基础太差，就会恐惧编程｜庖丁解牛

一旦遇到异常场景就容易恐慌：线上内存持续上涨、接口超时、数据库死锁、Nginx+FPM通信报错、文件上传漏洞、并发重复下单。当你能把Web请求从浏览器到内核、再到PHP进程、数据库的整条链路完整拆解，看懂每一个环节的约束，看懂BUG和性能问题的底层来源，你不再畏惧复杂业务、线上故障、底层面试题。报错出现之后，无法区分问题是前端、Nginx、网络、PHP代码、MySQL、Redis哪一层。整条链路涉

openEuler 社区

Linux信号全解析：从入门到精通

阶段核心概念关键函数信号产生终端按键、系统命令、函数调用、软件条件、硬件异常killraiseabortalarm信号保存未决(pending)、阻塞(block)、信号屏蔽字sigaddsetsigpending信号处理默认动作、忽略、自定义捕捉signalsigactionsigreturn🎯信号是进程间异步通信的一种方式，本质是操作系统对硬件中断的软件模拟。理解信号的关键在于理解它的异步性