博客

首先， 什么是欧拉回路。定义：

通过图（


无向图


或


有向图


）中所有边且每边仅通过一次通路称为欧拉通路，相应的回路称为欧拉回路。具有


欧拉回路


的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为


半欧拉图


。

要明确，有向图的欧拉回路和无向图的欧拉回路是不同的，其次，欧拉回路与欧拉通路也是不同的。

无向图：

欧拉回路：所有点的度都为偶数。度：即该点连接的路径，无向图中，不分出度与入度。

可以随便从一点出发，经过所有的边，再次回到这一点

欧拉通路：有两个点的度为奇数。此时可以从其中一个度为奇数点经过其他的点最终到达 另一个度为奇数的点

有向图：

入度：从一条边指向这一点，则这一点的入度+1

出度：有一条边从该点出发指向其他点，则这一点的出度+1

欧拉回路：所有点的入度等于该点的出度

欧拉通路：起点的入度等于起点的出度-1，终点的入度等于终点的出度+1，其他点的入 度都等于该点的出度

无向图存在欧拉回路的充要条件：

当且仅当该图所有顶点度数都为偶数且该图是连通图

有向图存在欧拉回路的充要条件:

当且仅当所有顶点的入度等于出度且该图是连通图

无向图的欧拉回路模板：

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int MX=1e5+5;
struct Edge{            //利用邻接表实现
    int v,nxt;
}E[MX*2];
int Head[MX],erear;
void edge_init(){
    erear=0;
    memset(Head,-1,sizeof(Head));
}
void edge_add(int u,int v){
    E[erear].v=v;
    E[erear].nxt=Head[u];
    Head[u]=erear++;
}

bool vis[MX];
int IN[MX],P[MX],sz;
void Fleury(int u){
    for(int i=Head[u];~i;i=Head[u]){
        int v=E[i].v;
        Head[u]=E[i].nxt;               //下一个点指向上一个点，即删去这条边
        if(vis[i|1]) continue;          //判断是否已经使用过
        vis[i|1]=1;
        Fleury(v);
    }
    P[++sz]=u;
}


int DU[MX];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    edge_init();
    memset(DU,0,sizeof(DU));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        edge_add(u,v);
        edge_add(v,u);
        DU[u]++;DU[v]++;
    }

    int cnt=0,rt;//a入度为奇数的个数
    for(int i=1;i<=n;i++){
        if(DU[i]%2==1){
            cnt++;rt=i;
        }
    }
    if(cnt!=2&&cnt!=0){
        printf("invalid\n");
        return 0;
    }
    if(cnt==0) rt=1;

    sz=0;
    Fleury(rt);
    for(int i=sz;i>=1;i--){
        printf("%d ",P[i]);
    }
    return 0;
}