欧拉回路 学习笔记

学习笔记

定义

设 $G(V,E)$ 是一张图
欧拉回路 : 图 $G$ 中经过每条边一次并且仅一次的回路.
欧拉路径 : 图 $G$ 中经过每条边一次并且仅一次的路径.
欧拉图 : 存在欧拉回路的图.
半欧拉图 : 存在欧拉路径但不存在欧拉回路的图.

定理与性质

以下的图中, 默认把孤立点删除, 因为这样不会影响原图是否为欧拉图.

定理1 : 无向图 $G$ 为欧拉图, 当且仅当 $G$ 为连通图且所有顶点的的度为偶数.
推论1 : 无向图 $G$ 为半欧拉图, 当且仅当 $G$ 为连通图, 且除了两个顶点的度为奇数外, 其他顶点的度为偶数.

定理2 : 有向图 $G$ 为欧拉图, 当且仅当 $G$ 为连通图且所有顶点的入度等于出度.
推论2 : 有线图 $G$ 为半欧拉图, 当且仅当 $G$ 为连通图, 且存在顶点 $u$ 的出度比入度大 $1$, 顶点 $v$ 的入读比出度大 $1$, 其他顶点的入度等于出度.

性质1 : 设 $C$ 是欧拉图 $G$ 的一个简单回路, 将 $C$ 中的边从图 $G$ 中删去得到一个新图 $G'$, 则 $G'$ 的每一个极大连通子图都存在一条欧拉回路.

性质2 :　设 $C_1,C_2$ 是图 $G$ 的两个没有公共边, 但有至少一个公共点的简单回路, 则可以将它们合并成一个新的简单回路 $C'$.

求欧拉回路

根据上面的定理, 我们已经可以判断欧拉图,
而求欧拉回路, 我们则需要用到上面的性质.

过程

1. 找出图 $G$ 中的一个简单回路, 并将它从图 $G$ 中删去.
2. 对图 $G$ 的每一个极大连通子图重复上述的过程.
3. 将图 $G$ 的极大连通子图的欧拉回路合并, 得到图 $G$ 的欧拉回路.

代码

欧拉回路
这个板子相对麻烦一点, 因为它要同时处理有向图和无向图的情况, 并且要求输出边的方案.

#include<bits/stdc++.h>
using namespace std;
bool b;
const int N=1e5+7;
const int M=2e5+7;
int ty,n,m,stk[M],top,frm[M],ans[M],ide[N],ode[N],blo[N],num;
int lst[N],nxt[2*M],to[2*M],id[2*M],op[2*M],tot;
bool vis[M],flag=1;
void add(int x,int y,int k){ nxt[++tot]=lst[x]; to[tot]=y; id[tot]=k; lst[x]=tot; }
void Euler_Circuit(){
    for(int i=1;i<=n;i++) 
        if(lst[i]){ stk[++top]=i; break; }
    while(top){
        int u=stk[top],i=lst[u];
        while(i&&vis[abs(id[i])]) i=nxt[i];
        if(i){
            int v=to[i];
            stk[++top]=v;
            frm[top]=id[i];
            lst[u]=i; 
            vis[abs(id[i])]=1;
        }
        else{
            ans[++ans[0]]=frm[top];
            top--;
        }
    }   
}
bool a;
int main(){
//  freopen("Euler.in","r",stdin);
    cin>>ty>>n>>m; int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(ty==1){
            add(x,y,i);
            add(y,x,-i);
            ide[x]++; ide[y]++;
            op[tot]=tot-1;
            op[tot-1]=tot;
        }
        else{
            add(x,y,i);
            ode[x]++; ide[y]++;
        }
    }
    for(int i=1;i<=n;i++)
        if(ty==1&&ide[i]%2){ flag=0; break; }
        else if(ty==2&&ide[i]!=ode[i]){ flag=0; break; }
    if(flag) Euler_Circuit();
    for(int i=1;i<=tot;i++) 
        if(!vis[abs(id[i])]){ flag=0; break; }
    if(!flag) puts("NO");
    else{
        puts("YES");
        for(int i=ans[0]-1;i>=1;i--) printf("%d ",ans[i]); putchar('\n');
    }
//  cerr << (&a-&b)/1048576.0<<endl;
    return 0;
}