欧拉回路模板

Posted on | In

​ 直接介绍复杂度最低（O(n+m)）的Hierholzer方法。它能帮我们找到一条欧拉回路。

​ 欧拉回路指不重复经过所有边的一条回路，在有向图中，如果满足每个点入度=出度则存在欧拉回路。在无向图中，满足每个点度数为偶数则存在欧拉回路。它具有这样的性质，即从一个欧拉图中去除一个小欧拉图，剩下的仍是欧拉图，去除一个点及其所连边同样。由此产生了Hierholzer算法。

​ 算法整体是一个dfs过程，总是尝试用一个回路来代替点u，于是我们对从u发出的边，只要是未标记的，就沿着它去搜下一个点，同时利用“引用”技巧将搜过确定下来的边删除，这样复杂度就不会退化。如果需要记录路径，选择用栈，在搜索过一个点所有的边后压栈这个点，这个时候栈中已经存了从该点出去的所有环。如果需要求字典序最小的，对边预先排序即可。

​ 对于无向图，我们依然建双向有向图，然后每次检查时要两条边均未标记才继续。

例题：cf547d

给出2e5棋盘上若干点，要求将其染成黑白两色，使得每一行每一列黑白数量之差不超过1.

我们作这样一个变换：将横纵坐标单独视为点，棋子所在的点视为x、y之间连边，意义就是通过对x染色，对y也产生了影响，我们可以将x点的边按出入分开染成不同的颜色，每条边都代表一个实际的（x，y）点，这样只要出边入边数量相差不超过1即可。实际上，我们可以对奇度顶点两两相连，虽然不是合法存在的点，最后输出结果不考虑即可，这样就凑成了欧拉图。

事实上，这道题中我们是先确定了一个欧拉图，然后通过这个算法获取欧拉回路中每条无向边的方向。其实也是一种构造，只不过借助了这个算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+3;

struct edge{
    int to,next;
}es[maxn<<2];
int head[maxn<<1];
int cnt=1;
inline void add(int u,int v){
    es[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
    es[++cnt]=(edge){u,head[v]};
    head[v]=cnt;
}
int du[maxn<<1];
int vis[maxn<<2];   //标记某条边是否被涂色

void dfs(int x){
    for(int &i=head[x];i;i=es[i].next){	//引用是降低复杂度的关键
        if(vis[i]||vis[i^1])			//如果一对边均未染色
            continue;
        vis[i]=1;
        dfs(es[i].to);
    }
    //记录回路就在这记录x即可
}
int n;
int main(){
    cin>>n;
    int x,y;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        y+=2e5;
        add(x,y);
        du[x]++,du[y]++;
    }
    int lst=0;
    for(int i=1;i<=4e5;i++){
        if(du[i]&1){
            if(lst) add(lst,i),lst=0;
            else lst=i;
        }
    }
    for(int i=1;i<=4e5;i++){
        if(du[i]){
            dfs(i);
        }
    }
    for(int i=1;i<=n;++i)
        putchar(vis[i<<1]?'b':'r'); //由于两条边中的一条肯定被标记，只需认定偶数边是一种颜色即可
    puts("");
    return 0;
}