欧拉回路 - 简书

欧拉回路

欧拉通路与欧拉回路

欧拉通路：对于图G来说，如果存在一条通路包含G中所有的边，则该通路成为欧拉通路，也称欧拉路径。
欧拉回路：如果欧拉路径是一条回路，那么称其为欧拉回路。
欧拉图 ：含有欧拉回路的图是欧拉图。

对有无向图G和有向图H：

图G存在欧拉路径与欧拉回路的充要条件分别是：
欧拉路径：图中所有奇度点的数量为0或2。
欧拉回路：图中所有点的度数都是偶数。

图H存在欧拉路径和欧拉回路的充要条件分别是：
欧拉路径：所有点的入度等于出度或者存在一点出度比入度大1(起点)，一点入度比出度大1(终点)，其他点的入度均等于出度。
欧拉回路：所有点的入度等于出度。

下面根据这道题目记录求欧拉回路的方法：

Acwing1184.欧拉回路

题目描述

给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

输入格式

第一行包含一个整数 t，t∈{1,2}，如果 t=1，表示所给图为无向图，如果 t=2，表示所给图为有向图。

第二行包含两个整数 n,m，表示图的结点数和边数。

接下来 m 行中，第 i 行两个整数 vi,ui，表示第 i 条边（从 1 开始编号）。

如果 t=1 则表示 vi 到 ui 有一条无向边。
如果 t=2 则表示 vi 到 ui 有一条有向边。
图中可能有重边也可能有自环。

点的编号从 1 到 n。

数据范围

$1≤n≤10^5,$
$0≤m≤2×10^5$

样例

输入
1
3 3
1 2
2 3
1 3

输出
YES
1 2 -3

算法Dfs

根据欧拉回路判断的充要条件，可以判定一个图是否是欧拉图，之后，我们可以利用dfs来找到一条欧拉回路：

以无向图为例，因为每个点的度都为偶数，所以我们从任意一个点出发，假设所有点的度数都为2，那么dfs一定会回到起点，从而形成一个回路(如果度数都为2，那么现在就是一条欧拉回路)，假设度数不全为2，有4,6,8...那么在dfs过程中，当走到这些点(假设走到点u)上时，可能会走到其他环上，但是由于度数是偶数，所以如果走到其他环上，最后也会回到点u，在dfs过后，一定会形成许多环，环与环之间有一个交点(在图中两个环可能有两个交点，但在dfs过程中只会选择一条边去走，所以这个"交点"的意义要分清楚)，在回溯过程中将这些点添加到答案中，就是一条欧拉回路。
有向图同理。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100100, M = 400100;

int h[N],e[M],ne[M],idx;
int ans[N*2],cnt;
bool used[M];
int din[N],dout[N];
int n,m,ver;

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs(int u){
    for(int &i = h[u]; ~i; ){
        if(used[i]){  //如果这条边用过了
            i = ne[i];   //删除这条边
            continue;
        }
        
        used[i] = true;  //标记这条边已使用
        if(ver == 1) used[i^1] = true;   //如果是无向图，那么这条边的反向边也要标记使用过了
        
        int t;
        if(ver == 1){
            t = i/2 + 1;
            if(i&1) t = -t;  //(0,1) (2,3) (4,5) 奇数编号是返回的边
            
        }else t = i+1;
        
        int j = e[i];
        i = ne[i];
        dfs(j);
        ans[cnt++] = t;
    }
}
int main()
{
    scanf("%d%d%d",&ver,&n,&m);
    memset(h,-1,sizeof h);
    
    for(int i = 0; i<m; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        if(ver == 1) add(b,a);  //无向边
        din[b]++, dout[a]++;   
    }
    
    if(ver == 1){
        for(int i = 1; i<=n; i++){
            if(din[i]+dout[i] &1){
                //无向图含欧拉回路的充要条件是每个点的度都为偶数
                puts("NO");
                return 0;
            }
        }
    }else{
        for(int i = 1; i<=n; i++){
            if(din[i] != dout[i]){
                //有向图含欧拉回路的充要条件是每个点的入度等于出度
                puts("NO");
                return 0;
            }
        }
    }
    
    for(int i = 1; i<=n; i++){
        if(~h[i]) {
            dfs(i);
            break;
        }
    }
    
    if(cnt < m){
        puts("NO");
        return 0;
    }
    
    puts("YES");
    for(int i = cnt-1; i>=0; --i){
        cout<<ans[i]<<" ";
    }
    return 0;
}