欧拉回路

sccc_ · 2025-07-26 17:34:29 · 个人记录

定义

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

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

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

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

性质

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

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

有向半欧拉图除两个特殊的点外，其他所有点入度等于出度，这两个特殊的点，一个点的出度 = 入度 + 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 接下来要访问的边，则代码为：

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

#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

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

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