欧拉路、欧拉回路学习笔记

· · 个人记录

欧拉路

如果图 G 中存在节点 S\neq T，使得 S 到 T 有一条路径不重不漏地经过所有边，则称 G 中存在欧拉路。

欧拉回路

如果图 G 中存在节点 S，使得有一条从 S 出发到 S 结束的路径不重不漏地经过所有边，则称 G 中存在欧拉路，G 是欧拉图。

欧拉路的判定法则

对于无向图 G，如果所有节点中有且仅有两个节点 S 和 T 度数为奇，其余点度数为偶，则 G 有欧拉路 S\leftrightarrow T。

对于有向图 G，如果所有节点中有且仅有一个节点 S 出度比入度大 1，有且仅有一个节点 T 入度比出度大 1，则 G 有欧拉路 S\to T。

联通图的欧拉路/欧拉回路寻找方法

首先根据欧拉路的判定法则确定起点 S。从 S 出发，每到达一个点 x：

  • 如果没有可用出边，则在栈顶记下 x，直接回溯。
  • 否则（如果存在一条出边 x 至 y）：
    1. 递归操作 y。
    2. 将边 x 至 y 标记为已用。

最后，从栈顶到栈底输出元素即为欧拉路/欧拉回路节点序列。

经过小数据手动验证后你会发现，倒序输出可以完美地解决“反悔”问题（一笔画完一个子图发现其实应该先画另一个子图再画这个），而且不打乱访问顺序（即不会在有向图中出现本来应该顺着走却逆着走了的情况）。

注：该方法既适用于欧拉路也适用于欧拉回路，既适用于无向图也适用于有向图。

附注：有些题目没有保证图联通，故须额外判定该欧拉子图是否能代表整个图为欧拉图。

再附注：非联通图不一定不是欧拉图/存在欧拉路的图（因为定义中给的是边不重不漏）。

【例】欧拉回路

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,m,tp,p,ans[N],in[N],out[N],deg[N],vis[N];
vector<pair<int,int> >G[N];
pair<int,int>stk[N];
void dfs(int s){
    stk[++tp]=make_pair(s,0);
    while(tp){
        int x=stk[tp].first,z=stk[tp].second;
        while(G[x].size()&&vis[abs(G[x].back().second)])G[x].pop_back();
        if(!G[x].size())ans[++p]=z,tp--;
        else {
            vis[abs(G[x].back().second)]=1;
            stk[++tp]=G[x].back();
        }
    }
}
int main(){
    cin>>t>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        G[u].push_back(make_pair(v,i));
        if(t==1)G[v].push_back(make_pair(u,-i)),deg[u]++,deg[v]++;
        else in[v]++,out[u]++;
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(t==1&&(deg[i]&1))cnt++;
        if(t==2&&in[i]!=out[i])cnt++;
    }
    if(cnt!=0){puts("NO");return 0;}
    for(int i=1;i<=n&&p<2;i++)p=0,dfs(i);
    if(p!=m+1){puts("NO");return 0;}
    puts("YES");
    for(int i=p-1;i;i--)cout<<ans[i]<<' ';
}

【例】单词游戏

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5 + 5;
vector<pair<int, int>>G[N];
bool vis[N];
int stack[N], top, ans[N], t, in[N], out[N], set[N], tot;
void reset() {
    for (int i = 1; i <= 26; i++)
        G[i].clear();

    top = t = tot = 0;
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    memset(vis, 0, sizeof(vis));
}
void euler(int st) {
    stack[++top] = st;
    int jx = 0;

    while (top > 0) {
        int x = stack[top];

        while (G[x].size() > 0 && vis[G[x].back().second])
            G[x].pop_back();

        if (G[x].size() > 0) {
            stack[++top] = G[x].back().first;
            vis[G[x].back().second] = 1;
        } else {
            top--;
            ans[++t] = x;
        }
    }
}
int main() {
    int task, n;
    string str;
    cin >> task;

    while (task--) {
        reset();
        cin >> n;
        int u, v;

        for (int i = 1; i <= n; i++) {
            cin >> str;
            u = str[0] - 'a' + 1, v = str[str.length() - 1] - 'a' + 1;
            G[u].push_back(make_pair(v, i));
            set[++tot] = u, set[++tot] = v;
            out[u]++, in[v]++;
        }

        sort(set + 1, set + tot + 1);
        tot = unique(set + 1, set + tot + 1) - set - 1;
        int o1 = -1, o2 = -1, r1 = 0, r2 = 0, flag = 1;

        for (int i = 1; i <= tot; i++) {
            if (out[set[i]] == in[set[i]] + 1)
                r1++, o1 = set[i];
            else if (in[set[i]] == out[set[i]] + 1)
                r2++, o2 = set[i];
            else if (in[set[i]] != out[set[i]]) {
                flag = 0;
                break;
            }
        }

        if (!(r1 == 1 && r2 == 1 || r1 == 0 && r2 == 0))
            flag = 0;

        if (!flag) {
            puts("The door cannot be opened.");
            continue;
        }

        if (r1 == 0 && r2 == 0)
            o1 = set[1];

        euler(o1);

        if (t != n + 1)
            flag = 0;

        if (!flag) {
            puts("The door cannot be opened.");
            continue;
        }

        puts("Ordering is possible.");
    }
}