欧拉回路_牛客博客

欧拉路径

在一个图中，由i点出发，将每个边遍历一次最终到达j点的一条路径。
欧拉回路：i=j时的欧拉路径。

一些概念

图中的度：就是指和该顶点相关联的边数

在有向图中，度又分为入度和出度。
入度 (in-degree) ：以某顶点为弧头，终止于该顶点的弧的数目称为该顶点的入度。
出度 (out-degree) ：以某顶点为弧尾，起始于该顶点的弧的数目称为该顶点的出度。

在某顶点的入度和出度的和称为该顶点的度

无向图

存在欧拉回路的充要条件是所有的点的度数均为偶数
因为每个点的度数为偶数，所以可以将整个图看做由数个环嵌套而成，因为环一定能找到一条欧拉回路，所以整个图也能找到欧拉回路。

在这里插入图片描述 )

存在欧拉路径的充要条件是度数为奇数的点的数量为0个或者2个
给一欧拉回路，切断回路中的任一条边，被切断的边的两个顶点即可作为这条欧拉路径的终点起点。

有向图

存在欧拉回路的充要条件是所有的点的出度均等于入度
对于每一个点，每次进入这个节点，就一定有一条路可以出去，因此必定存在一条欧拉回路。

在这里插入图片描述 )

存在欧拉路径的充要条件是
①：欧拉回路的情况 ②：所有点中出度比入度大1的点有一个，入度比出度大1的点有一个，不允许有大几个的情况

此处讨论均是基于存在欧拉回路的情况（存在条件上面已给出）

算法的朴素表达：

对于欧拉图，从一个节点出发，随便往下走（走过之后需要标记一下，下次就不要来了），必然也在这个节点终止（因为除了起始节点，其他节点的度数都是偶数，只要能进去就能出来）。这样就构成了一个圈，但因为是随便走的，所以可能会有些边还没走过就回来了。我们就从终止节点逆着往前查找，直到找到第一个分叉路口，然后从这个节点出发继续上面的步骤，肯定也是可以找到一条回到这个点的路径的，这时我们把两个圈连在一起。当你把所有的圈都找出来后，整个欧拉回路的寻找就完成了。

套圈法找欧拉回路

实现：
任取一个起点,开始下面的步骤
如果该点没有相连的点，就将该点加进路径中然后返回。
如果该点有相连的点，就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点，删除一个点）
处理当前的点,删除和这个点相连的边, 在它相邻的点上重复上面的步骤,把当前这个点加入路径中.

例题欧拉回路

题目链接：https://loj.ac/problem/10105
欧拉回路的模板题

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int M=2e5+10;
int head[M],nex[M*2],to[M*2],w[M*2];
int cnt=1,vis[M],in[M],out[M];
int n,m,t,xx;
stack<int>k;
void add(int x,int y,int c)
{
    nex[++cnt]=head[x];
    to[cnt]=y;
    w[cnt]=c;
    head[x]=cnt;
}
void dfs(int x)
{
    //这里要加上&，不然会超时（我也不知道为什么）
    for(int &i=head[x];i;i=nex[i])
    {
        int tt=to[i];
        int gg=i;
        if(!vis[i/2])
        {
            vis[i/2]=1;
            xx++;
            dfs(tt);
            k.push(w[gg]);
        }
    }
}
int main()
{
    cin>>t;
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v,i);
        if(t==1)add(v,u,-i);
        else cnt++;
        out[u]++,in[v]++;
    }
    bool flag=true;
    if(t==1)
    {
        for(int i=1;i<=n;i++)
            if((in[i]+out[i])%2)
            {
                flag=false;
                break;
            }
    }
    else {
        for(int i=1;i<=n;i++)
            if(in[i]!=out[i])
            {
                flag=false;
                break;
            }
    }
    if(flag)
    {
        dfs(u);
        if(xx==m)
        {
            cout<<"YES"<<endl;
            while(!k.empty())
            {
                cout<<k.top()<<" ";
                k.pop();
            }
        }
        else cout<<"NO\n"<<endl;
    }
    else cout<<"NO\n"<<endl;
    return 0;
}

欧拉回路