直接介绍复杂度最低（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;
}
|
