欧拉回路

定义

欧拉回路是指从某一顶点出发，通过每条边恰好一次后，最终回到起始顶点的路径。

欧拉通路是从某一顶点出发，不重复地通过所有边后，到达另一个不同顶点的路径。

欧拉图是有欧拉回路的图。

半欧拉图是有欧拉通路没有欧拉回路的图。

性质

有向欧拉图每个点的入度等于出度。

无向欧拉图所有点度数为偶数。

有向半欧拉图除两个特殊的点外，其他所有点入度等于出度，这两个特殊的点，一个点的出度 = 入度 + 1（作为起点），另一个点的入度 = 出度 + 1（作为终点）。

P7771 【模板】欧拉路径

因为欧拉图每条边只走一次，我们可以用普通的方法，标记 + 枚举边暴力走。

void dfs(int u) {
	for (int i = 0; i < nbr[u].size(); i++) {
		if (vis[u][i] == 0) {
			vis[u][i] = 1;
			dfs(nbr[u][i]);
		}
	}
	v.push_back(u);
	return;
}

但这样会超时。

当前弧优化

定义

head_u

为点

u

接下来要访问的边，则代码为：

CPP

void dfs(int u) {
	for (int i = head[u]; i < nbr[u].size(); i = head[u]) {
		head[u] = i + 1;
		dfs(nbr[u][i]);
	}
	v.push_back(u);
	return;
}

CPP

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, in[N], out[N], head[N];
vector<int> nbr[N], v;

void dfs(int u) {
	for (int i = head[u]; i < nbr[u].size(); i = head[u]) {
		head[u] = i + 1;
		dfs(nbr[u][i]);
	}
	v.push_back(u);
	return;
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		nbr[u].push_back(v);
		in[v]++, out[u]++; 
	}
	int cnt1 = 0, cnt2 = 0, root = 1;
	for (int i = 1; i <= n; i++) {
		if (out[i] - in[i] == 1) {
			cnt1++;
			root = i;
		} else if (in[i] - out[i] == 1) {
			cnt2++;
		}
	}
	if (!(cnt1 == 0 && cnt2 == 0) && !(cnt1 == 1 && cnt2 == 1)) {
		cout << "No";
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		sort(nbr[i].begin(), nbr[i].end());
	}
	dfs(root);
	for (int i = v.size() - 1; i >= 0; i--) {
		cout << v[i] << ' ';
	}
	return 0;
}

P1341 无序字母对

无向图，最后输出字典序最小的欧拉路径，可以用领接矩阵存图。

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

using namespace std;

const int N = 60;
int n, nbr[105][105], in[105];
string v;

void dfs(int u) {
	for (int i = 0; i <= N; i++) {
		if (nbr[u][i]) {
			nbr[u][i]--, nbr[i][u]--;
			dfs(i);
		}
	}
	v.pb(u + 'A');
	return;
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		char a, b;
		cin >> a >> b;
		a -= 'A', b -= 'A', nbr[a][b]++, nbr[b][a]++, in[a]++, in[b]++;
	}
	int cnt = 0, root = -1;
	for (int i = 0; i <= N; i++) {
		if (in[i] & 1) {
			cnt++;
			if (root == -1) {
				root = i;
			}
		}
	}
	if (cnt && cnt != 2) {
		cout << "No Solution";
		return 0;
	}
	if (cnt == 0) {
		for (int i = 0; i <= N; i++) {
			if (in[i]) {
				root = i;
				break;
			}
		}
	}
	dfs(root);
	if (v.size() <= n) {
		cout << "No Solution";
		return 0;
	}
	for (int i = v.size() - 1; i >= 0; i--) {
		cout << v[i];
	}
	return 0;
}

P1333 瑞瑞的木棍

首先用并查集判断图是否连通，再用欧拉路径的性质判断是不是欧拉路径。

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

using namespace std;

const int N = 5e5 + 10;

int n, m, in[N], fa[N], id;
map<string, int> mp;
string u, v;
	
int find(int x) {
	return (fa[x] == x ? x : fa[x] = find(fa[x]));
}

void unionn(int x, int y) {
	x = find(x), y = find(y);
	if (x != y) {
		fa[x] = y;
	}
	return;
}
	
signed main() {
	for (int i = 1; i <= N; i++)
		fa[i] = i;
	while (cin >> u >> v) {
		if (!mp.count(u)) {
			mp[u] = ++id;
		}
		if (!mp.count(v)) {
			mp[v] = ++id;
		}
		in[mp[u]]++, in[mp[v]]++;
		unionn(mp[u], mp[v]);
	}
	int root = find(1);
	for (int i = 2; i <= id; i++) {
		if (find(i) != root) {
			cout << "Impossible";
			return 0;
		}
	}
	int cnt = 0;
	for (int i = 1; i <= id; i++) {
		if (in[i] & 1)
			cnt++; 
	}
	if (cnt && cnt != 2)
		cout << "Impossible";
	else
		cout << "Possible";
	return 0;
}

AT_abc286_g [ABC286G] Unique Walk

可以把边分为关键边（只能走一次）和非关键边（能走多次）。

再把非关键边连通块缩成一个点，可以用并查集。

再判断欧拉路径即可。

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

using namespace std;

const int N = 2e5 + 10;

int n, m, k, fa[N], u[N], v[N], vis[N], deg[N];

int find(int x) {
	return (fa[x] == x ? fa[x] : fa[x] = find(fa[x]));
}

void unionn(int x, int y) {
	x = find(x), y = find(y);
	if (x != y) {
		fa[x] = y;
	}
	return;
}

signed main() {
	cin.tie(0), cout.tie(0)->sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}	
	for (int i = 1; i <= m; i++) {
		cin >> u[i] >> v[i];
	}
	cin >> k;
	for (int i = 1; i <= k; i++) {
		int p;
		cin >> p;
		vis[p] = 1;
	}
	for (int i = 1; i <= m; i++) {
		if (!vis[i]) {
			unionn(u[i], v[i]);
		}
	}
	for (int i = 1; i <= m; i++) {
		if (vis[i]) {
			int fu = find(u[i]), fv = find(v[i]);
			if (fu != fv) {
				deg[fu]++, deg[fv]++;
			}
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		cnt += deg[i] & 1;
	}
	if (cnt == 0 || cnt == 2) {
		cout << "Yes\n";
	} else {
		cout << "No\n";
	}
	return 0;
}

P3520 [POI 2011] SMI-Garbage

因为只有开始与结尾不相同的边才要跑，所以把要产生变化的边建边跑欧拉路径就行。

CPP

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

using namespace std;

const int N = 2e6 + 10;

int n, m, ANS, instk[N], vis[N], head[N], vis_e[N], cnt, deg[N];
stack<int> stk;
vector<int> res[N];

struct Edge {
	int v, w, nxt;
} edge[N];

void add_edge(int u, int v, int w) {
	edge[++cnt].v = v, edge[cnt].w = w, edge[cnt].nxt = head[u], head[u] = cnt;
	return;
}

void dfs(int u) {
	vis[u] = 1;
	for (int i = head[u]; i; i = head[u]) {
		head[u] = edge[i].nxt;
		if (vis_e[i])
			continue;
		vis_e[i] = vis_e[i ^ 1] = 1;
		int v = edge[i].v;
		dfs(v);
		if (instk[v]) {
			res[++ANS].push_back(v);
			while (stk.top() != v) {
				res[ANS].push_back(stk.top());
				instk[stk.top()] = 0;
				stk.pop();
			}
			res[ANS].push_back(v);
		} else {
			stk.push(v), instk[v] = 1;
		}
	}
}

signed main() {
	cin >> n >> m;
	cnt = 1;
	while (m--) {
		int u, v, s, t;
		cin >> u >> v >> s >> t;
		if (s ^ t) {
			add_edge(u, v, 0);
			add_edge(v, u, 0);
			deg[u]++, deg[v]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (deg[i] & 1) {
			cout << "NIE\n";
			return 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i] && deg[i]) {
			dfs(i);
			res[++ANS].push_back(i);
			while (!stk.empty()) {
				res[ANS].push_back(stk.top());
				instk[stk.top()] = 0;
				stk.pop();
			}
		}
	}
	cout << ANS << '\n';
	for (int i = 1; i <= ANS; i++) {
		int len = res[i].size();
		cout << len - 1 << ' ';
		for (int j = 0; j < len; j++) {
			cout << res[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

文章操作

定义

性质