概念
- 欧拉回路：通过图中每条边恰好一次的回路
- 欧拉通路：通过图中每条边恰好一次的通路
- 欧拉图：具有欧拉回路的图
- 半欧拉图：具有欧拉通路但不具有欧拉回路的图
判断存在欧拉回路/欧拉通路
有向图
- 欧拉回路：图除一个连通分量之外其余都是孤立点，且所有点入度等于出度。
- 欧拉通路：有欧拉回路；或图除一个连通分量之外其余都是孤立点，且至多 1 个点出度比入度大 1，至多 1 个点入度比出度大 1，其余点入度等于出度。（特别的，此时通路起点是出度比入度大 1 的点）
无向图
总结
对于一张图，判断是否存在欧拉回路/通路要做两件事情：
- 把这张图当作无向图，判断是否连通（可以用并查集，或者 dfs）
- 判断特殊点的个数是否符合要求（奇点、出度入度差 1 的点）
寻找欧拉回路/欧拉通路
使用 dfs，每经过一条边就把这条边删了。最后在递归结束的时候加入栈，即可正确找出路径。
顺带一提，如果要求答案的边，可以在经过一条边递归下一个节点结束之后，把这条边加入答案的栈。
来看一个例子：
对于这张图，实际的运行情况如下：
搜索 1
├───搜索 2，删除边(1->2)
│ ├───搜索 3，删除边(1->3)
│ │ ├───搜索 1，删除边(3->1)
│ │ │ ├───搜索 4，删除边(1->4)
│ │ │ │ ├───搜索 5，删除边(4->5)
│ │ │ │ │ ├───搜索 1，删除边(5->1)
│ │ │ │ │ │ 1 入栈
│ │ │ │ │ ├───搜索 6，删除边(5->6)
│ │ │ │ │ │ ├───搜索 7，删除边(6->7)
│ │ │ │ │ │ │ ├───搜索 5，删除边(7->5)
│ │ │ │ │ │ │ │ 5入栈
│ │ │ │ │ │ │ 7 入栈
│ │ │ │ │ │ 6 入栈
│ │ │ │ │ 5 入栈
│ │ │ │ 4 入栈
│ │ │ 1 入栈
│ │ 3 入栈
│ 2 入栈
1 入栈
最终栈顺序： (栈顶) 1 2 3 1 4 5 6 7 5 1 (栈底)
邻接矩阵实现
邻接矩阵的实现很简单，只需要直接把对于的边删除即可。复杂度为 O(n2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
| stack<int> ans;
int G[N][N];
void dfs(int u){
for(int v=1;v<=n;v++){
if(G[u][v]){
G[u][v]=G[v][u]=0;
dfs(v);
}
}
ans.push(u);
}
|
邻接表实现
用邻接矩阵找欧拉回路的时间复杂度是 O(n2)，如果使用邻接表，可以做到 O(n+m) 的时间复杂度。
关键是要处理好删边的问题，邻接表的删边就没有邻接矩阵那么简单。下面给出一种使用 vector 数组的实现（也可以使用链式前向星来实现）。
有向图
对于一个有向图来说，删边很容易，只需要增加一个 cur 数组，记录当前每个节点现在已经遍历到第几条出边了（和 dinic 算法的 dfs 过程思想一致），因为每个节点访问过的边一定是按顺序从前往后访问的（而在无向图中，一条边的可能因为其反向边被访问了而不能访问，所以需要其他处理）。
具体实现：
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
vector<int> G[N];
int cur[N];
int in[N],out[N];
int fa[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int i,int j){
fa[find(i)]=find(j);
}
stack<int> ans;
void dfs(int u){
for(int& i=cur[u];i<G[u].size();){
i++;
dfs(G[u][i-1]);
}
ans.push(u);
}
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
out[u]++,in[v]++;
merge(u,v);
}
for(int i=1;i<=n;i++)sort(G[i].begin(),G[i].end());
int start = n;
int cnt = 0;
for(int i=1;i<=n;i++){
if(find(i)!=find(1)){
puts("No");
return 0;
}
if(abs(in[i]-out[i])>1){
puts("No");
return 0;
}
if(in[i]-out[i]==1)cnt++;
else if(out[i]-in[i]==1)cnt++,start=i;
}
if(cnt > 2){
puts("No");
return 0;
}
if(cnt==0)start=1;
dfs(start);
while(ans.size()){
printf("%d ",ans.top());
ans.pop();
}
return 0;
}
|
无向图
而对于一个无向图，要同时把它的反向边一起删除，一种实现是在记录边的时候同时记录它的反向边是这条边的终点的第几条出边，然后在边上同时增加一个删除标记，并且仍然保留 cur 数组，这样复杂度仍是 O(n+m)。即采用如下存图方式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| struct Edge{
int to;
int rev;
bool flag;
};
int cur[N];
vector<Edge> G[N];
int deg[N];
void add_edge(int u,int v){
G[u].push_back(Edge{v,(int)G[v].size(),true});
G[v].push_back(Edge{u,(int)G[u].size()-1,true});
deg[u]++,deg[v]++;
}
|
完整的实现如下：
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct Edge{
int to;
int rev;
bool flag;
};
int cur[N];
vector<Edge> G[N];
int deg[N];
int fa[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int i,int j){
fa[find(i)]=find(j);
}
stack<int> ans;
void dfs(int u){
for(int& i=cur[u];i<G[u].size();){
i++;
if(!G[u][i-1].flag)continue;
G[u][i-1].flag = 0;
G[G[u][i-1].to][G[u][i-1].rev].flag=0;
dfs(G[u][i-1].to);
}
ans.push(u);
}
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(Edge{v,(int)G[v].size(),true});
G[v].push_back(Edge{u,(int)G[u].size()-1,true});
deg[u]++,deg[v]++;
merge(u,v);
}
int start = n;
int cnt = 0;
for(int i=1;i<=n;i++){
if(find(i)!=find(1)){
puts("No");
return 0;
}
if(deg[i]%2==1){
cnt++;
start=min(start,i);
}
}
if(cnt > 2){
puts("No");
return 0;
}
if(cnt==0)start=1;
dfs(start);
while(ans.size()){
printf("%d ",ans.top());
ans.pop();
}
return 0;
}
|
