欧拉路径与欧拉回路

二gou子 · 2021-11-15 21:01:04 · 个人记录

问题引入

几乎所有人小时候肯定都听说过“一笔画”的游戏，就是给出一张图，用一笔经过所有的边，实际上这就是一个找欧拉路径的过程

基本概念

（以下都是自己瞎诌的，但是感觉也没啥问题）

欧拉路径：不重复的经过每一条边的路径。欧拉回路：起点与终点相同的欧拉路径。首先来探求一下它们存在的条件：

如果是无向图：

那么这个图存在欧拉路径当且仅当：至多有两个点度数为奇数，剩下的点度数都是偶数（两个奇数点当然就是起点和终点了）。这个图存在欧拉回路当且仅当：所有点的度数都是偶数（很好理解，每个点都是一进一出嘛）

如果是有向图：

那么这个图存在欧拉路径当且仅当：至多存在一个点入度是出度 +1 （起点），至多存在一个点出度是入度 +1 （终点），剩下的点入度出度必须相等。这个图存在欧拉回路当且仅当：所有点的入度出度都相等（还是一进一出）

算法流程

那么我们已经掌握了判定条件，只需要证明至少有一种方案找到合法的欧拉路径/欧拉回路就行了。事实上直接 \rm dfs 求解就行了，至于证明貌似我也不大会……~~反之是对的就是了~~

具体地，我们直接以某个点（在某些图中起点是固定的）为起点 \rm dfs 就好了，但是注意，在输出方案的时候，我们不能遍历到一个点就接着塞到答案数组里最后输出，而是应该用一个栈，递归完当前这个点所有出边再把这个点塞进栈中，最后倒序输出。那么为什么不能直接塞呢？玩一下这组数据就明白了：

如果按照链式前向星存图，就会先进入 1,2 ，然后发现在 2 里面出不来了，最后我们得到的答案就是 1,2,3,1 ，但显然正确的路径应该是 1,3,1,2 ，出现这种情况的原因就是后面的环没有跑到，所以我们递归求解完之后再塞入栈中，就可以解决这种问题。同时，为了优化复杂度，我们应用类似网络流当前弧优化的手段，走过的边不再走，就能把时间复杂度优化到 O(n+m) ，而这已经是非常优秀的时间复杂度了，~~毕竟读入也就是这个复杂度了~~

例题剖析

P7771 【模板】欧拉路径

直接套上板子就好了，由于题目让我们输出字典序最小的方案，所以为了便于实现，我们使用 \rm vector 存图，排序会很容易。但是时间复杂度同时也变成了 O(m\log m) ，虽然过题已经绰绰有余了，~~但是如果你非要用桶排或者基数排序优化到线性也不是不行~~

Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=1e6+5;
int n,m,top;
int in[N],out[N],ans[N],now[N];
vector<int> edge[N];
bool vis[N];
void dfs(int x){
    for(int i=now[x];i<(int)edge[x].size();i=now[x]){
        now[x]=i+1;
        int y=edge[x][i];
        dfs(y);
    }
    ans[++top]=x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        edge[x].push_back(y);
        in[y]++;out[x]++;
    }

    int cnt1=0,cnt2=0,pos1=0;
    bool flg=0;
    for(int i=1;i<=n;i++){
        if(out[i]-in[i]==1){
            cnt1++;
            pos1=i;
        }       
        else if(in[i]-out[i]==1) cnt2++;
        else if(in[i]!=out[i]) flg=1;
    }
    if(cnt1>1||cnt2>1) flg=1;
    if(flg){
        printf("No\n");
        return 0;
    }

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

    if(pos1) dfs(pos1);
    else dfs(1);

    for(int i=top;i>=1;i--) printf("%d ",ans[i]);
    return 0;
}
/*
3 3
1 3
3 1
1 2
*/

实战演练

LOJ #10105. 「一本通 3.7 例 1」欧拉回路

这个题相对于上个题来说就更加全面了，不过还是很基础的板子，只要注意细节就好了

Code

这题有一个坑点那就是 1~n 不一定每个点都出现了……感觉有点离谱。不过 LOJ 很良心给看数据，所以也能很快发现这个问题。但同时还有图不联通的毒瘤数据，所以也要注意特判

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=4e5+5;
int op,n,m,top,tot=1;
int head[N],ver[M],Nxt[M],edge[M],in[N],out[N],ans[M];
bool vis[M],v[N];
void add(int x,int y,int z){
    ver[++tot]=y;
    edge[tot]=z;
    Nxt[tot]=head[x];
    head[x]=tot;
}
void dfs(int x){
    v[x]=1;
    for(int i=head[x];i;i=head[x]){
        head[x]=Nxt[i];
        if(op==1){
            if(vis[i]||vis[i^1]) continue;
        }
        else{
            if(vis[i]) continue;
        }

        if(op==1) vis[i]=vis[i^1]=1;
        else vis[i]=1;

        dfs(ver[i]);
        ans[++top]=edge[i];
    }
}
int main()
{
    scanf("%d",&op);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        in[y]++;out[x]++;
        add(x,y,i);
        if(op==1) add(y,x,-i); 
    }

    for(int i=1;i<=n;i++){
        if(op==1){
            if((in[i]+out[i])&1){
                printf("NO\n");
                return 0;
            }
        }
        else{
            if(in[i]!=out[i]){
                printf("NO\n");
                return 0;
            }
        }
    }

    bool flg=0;
    for(int i=1;i<=n;i++){
        if(v[i]) continue;
        if(in[i]+out[i]>0){
            if(flg){
                printf("NO\n");
                return 0;
            }
            flg=1;
            dfs(i);
        }
    }

    printf("YES\n");
    for(int i=top;i>=1;i--) printf("%d ",ans[i]);

    return 0;
}