欧拉路问题

Hihocoder上面每周都会提供一个算法题,并且形成了许多的系列,每个系列循序渐进,如果用心,就可以在上面学到许多的算法知识。

今天在Hihocoder上研究了其欧拉路问题的系列,对应的链接:

#1176 : 欧拉路·一
#1181 : 欧拉路·二
#1182 : 欧拉路·三

问题一

描述

小Hi和小Ho最近在玩一个解密类的游戏,他们需要控制角色在一片原始丛林里面探险,收集道具,并找到最后的宝藏。现在他们控制的角色来到了一个很大的湖边。湖上有N个小岛(编号1..N),以及连接小岛的M座木桥。每座木桥上各有一个宝箱,里面似乎装着什么道具。

湖边还有一个船夫,船夫告诉主角。他可以载着主角到任意一个岛上,并且可以从任意一个岛上再载着主角回到湖边,但是主角只有一次来回的机会。同时船夫告诉主角,连接岛屿之间的木桥很脆弱,走过一次之后就会断掉。

因为不知道宝箱内有什么道具,小Hi和小Ho觉得如果能把所有的道具收集齐肯定是最好的,那么对于当前岛屿和木桥的情况,能否将所有道具收集齐呢?

举个例子,比如一个由6个小岛和8座桥组成的地图:

主角可以先到达4号小岛,然后按照4->1->2->4->5->6->3->2->5的顺序到达5号小岛,然后船夫到5号小岛将主角接回湖边。这样主角就将所有桥上的道具都收集齐了。

输入

第1行:2个正整数,N,M。分别表示岛屿数量和木桥数量。1≤N≤10,000,1≤M≤50,000

第2..M+1行:每行2个整数,u,v。表示有一座木桥连接着编号为u和编号为v的岛屿,两个岛之间可能有多座桥。1≤u,v≤N

输出

第1行:1个字符串,如果能收集齐所有的道具输出“Full”,否则输出”Part”。

解题思路

这个问题就是一笔画问题,更正式的名称叫做欧拉路问题 ,其定义是:

给定无孤立结点图G,若存在一条路,经过图中每边一次且仅一次,该条路称为欧拉路。

欧拉路问题是有判定条件的:(证明略)

一个无向图存在欧拉路当且仅当该图是连通的且有且只有2个点或0个点的度数是奇数。若有2个点的度数是奇数,则此时这两个点只能作为欧拉路径的起点和终点。

据此,可以轻松的写出代码。

C++代码

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
#include <iostream>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

int N;
vector<vector<int> > matrix;
bool isConnected() {
vector<bool> vst(N, false);
queue<int> q;
q.push(0);
vst[0] = true;
int vcnt = 0;
while (!q.empty()) {
int t = q.front(); q.pop();
vcnt++;
vector<int>::iterator it = matrix[t].begin();
for (; it != matrix[t].end(); it++) {
if (vst[*it]) continue;
vst[*it] = true;
q.push(*it);
}
}
if (vcnt == N) return true;
return false;
}

int main() {
// freopen("..\\input.txt", "r", stdin);
int M;
cin >> N >> M;
matrix = vector<vector<int> >(N);
vector<int> du(N, 0);
int odd = 0;
while (M--) {
int u, v;
cin >> u >> v;
u--, v--;
matrix[u].push_back(v);
matrix[v].push_back(u);
odd += ((++du[u]) % 2 == 0) ? -1 : 1;
odd += ((++du[v]) % 2 == 0) ? -1 : 1;
}
if ((odd == 0 || odd == 2) && isConnected())
cout << "Full" << endl;
else
cout << "Part" << endl;
}

问题二

描述

在上一回中小Hi和小Ho控制着主角收集了分散在各个木桥上的道具,这些道具其实是一块一块骨牌。

主角继续往前走,面前出现了一座石桥,石桥的尽头有一道火焰墙,似乎无法通过。

小Hi注意到在桥头有一张小纸片,于是控制主角捡起了这张纸片,只见上面写着:

将M块骨牌首尾相连放置于石桥的凹糟中,即可关闭火焰墙。切记骨牌需要数字相同才能连接。
——By 无名的冒险者

小Hi和小Ho打开了主角的道具栏,发现主角恰好拥有M快骨牌。

小Ho:也就是说要把所有骨牌都放在凹槽中才能关闭火焰墙,数字相同是什么意思?

小Hi:你看,每一块骨牌两端各有一个数字,大概是只有当数字相同时才可以相连放置,比如:

小Ho:原来如此,那么我们先看看能不能把所有的骨牌连接起来吧。

输入

第1行:2个正整数,N,M。分别表示骨牌上出现的最大数字和骨牌数量。1≤N≤1,000,1≤M≤5,000

第2..M+1行:每行2个整数,u,v。第i+1行表示第i块骨牌两端的数字(u,v),1≤u,v≤N

输出

第1行:m+1个数字,表示骨牌首尾相连后的数字

比如骨牌连接的状态为(1,5)(5,3)(3,2)(2,4)(4,3),则输出”1 5 3 2 4 3”

你可以输出任意一组合法的解。

解题思路

很容易看书这题其实就是一个求欧拉路路径的问题,在问题一中我们解决了欧拉路的判定,这里需要求出任意一条欧拉路的路径(不唯一)。

求欧拉路的路径可以使用如下的算法:

Fleury算法求欧拉路径

路径的起点

从问题一的分析可以得知,当图中存在度为奇数的点时,则起点必须是度为奇数的点,否则起点可以为任意节点。

部分路径的扩充

我们来看一个例子:

首先,以1为起点,任意需找一条路径,直到没有边时停止,此时可以得到一个部分路径:

1
L1: 1-2-6-5-1

这时如果在节点2处进行一次路径扩充,则可以得到扩充路径:

1
L2: 2-3-7-2

同理,可以对L2进行路径扩充,得到新的扩充路径:

1
L3: 3-4-8-3

至此,所有的路径都已经被覆盖到,此时我们需要做的就是将L1、L2、L3这三条路径合并起来,这可以用DFS来实现。伪代码为:

1
2
3
4
5
6
7
DFS(u):
While (u存在未被删除的边e(u,v))
删除边e(u,v)
DFS(v)
End
PathSize ← PathSize + 1
Path[ PathSize ] ← u

C++代码

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
#include <iostream>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

int N;
vector<vector<int> > matrix;

void dfs(int n) {
for (int i = 0; i < N; i++) {
if (matrix[n][i]) {
matrix[n][i]--;
matrix[i][n]--;
dfs(i);
}
}
cout << n+1 << ' ';
}

int main() {
// freopen("..\\input.txt", "r", stdin);
int M;
cin >> N >> M;
matrix = vector<vector<int> >(N, vector<int>(N, 0));
vector<int> du(N, 0);
int oddV = 0;
while (M--) {
int u, v;
cin >> u >> v;
u--, v--;
matrix[u][v]++;
matrix[v][u]++;
if (++du[u] % 2 == 1) oddV = u;
if (++du[v] % 2 == 1) oddV = v;
}
dfs(oddV);
cout << endl;
}

注意

虽然此题可以抽象为求无向连通图的欧拉路问题,但是题中并没有说明不存在两个一样的骨牌,所以需要考虑重边的问题,即两个节点之间的边数可能大于1

问题三

描述

小Hi和小Ho破解了一道又一道难题,终于来到了最后一关。只要打开眼前的宝箱就可以通关这个游戏了。

宝箱被一种奇怪的机关锁住:

这个机关是一个圆环,一共有2^N个区域,每个区域都可以改变颜色,在黑白两种颜色之间切换。

小Ho控制主角在周围探索了一下,果然又发现了一个纸片:

机关黑色的部分表示为1,白色的部分表示为0,逆时针连续N个区域表示一个二进制数。打开机关的条件是合理调整圆环黑白两种颜色的分布,使得机关能够表示0~2^N-1所有的数字。
我尝试了很多次,终究没有办法打开,只得在此写下机关破解之法。
——By 无名的冒险者

小Ho:这什么意思啊?

小Hi:我给你举个例子,假如N=3,我们通过顺时针转动,可以使得正下方的3个区域表示为:

因为黑色表示为1,白色表示为0。则上面三个状态分别对应了二进制(001),(010),(101)

每转动一个区域,可以得到一个新的数字。一共可以转动2^N次,也就是2^N个数字。我们要调整黑白区域的位置,使得这2^N个数字恰好是0~2^N-1

小Ho:我懂了。若N=2,则将环上的黑白色块调整为”黑黑白白”,对应了”1100”。依次是”11”,”10”,”00”,”01”四个数字,正好是0~3。那么这个”黑黑白白”就可以打开机关了咯?

小Hi:我想应该是的。

小Ho:好像不是很难的样子,我来试试!

提示:有向图欧拉回路

输入

第1行:1个正整数,N。1≤N≤15

输出

第1行:1个长度为2^N的01串,表示一种符合要求的分布方案

解题思路

容易得出,需要找出一种0~2^N-1这2^N个数字的排列,使得相邻的数字之间满足一种位移关系,这种关系为:

第i个数在左移1位后,右边补0或1,可以得到第i+1个数。例如001在左移一位后,可以得到010和011,所以1的右边可以是2和3。

如果我们构造出一个图,以图中的边来表示0~2^N-1这2^N个数字,并且满足这种位移关系的边相连(有向) ,那么我们的问题就转化为了求有向图的欧拉回路问题。

关于有向图的欧拉路

对于有向图,其存在欧拉路的判定条件为:

该有向图是连通的,并满足有且仅有0个或2个节点的入度不等于出度。若所有节点都满足入度等于出度,则一定存在欧拉回路(起点与终点相同);若有2个节点入度不等于出度,则必须满足其中一个节点入度比出度多1(终点), 另一个节点出度比入度多1(起点)。

如何构造这样的图呢?我们要求满足关系的边是相连的,例如001与010、011都满足关系,于是需要图中某个节点满足有一条入边001,有2条出边010、011。这三条边共有的部分是01,所以可以用01来表示这个节点。于是,对于N=3,我们可以构造出如下的图:

可以看出,我们只需要以0~2^(N-1)-1这2^(N-1)个点为节点来构造图就可以了,而边XYZ则可以表示从XY节点指向YZ节点的边。且这样构造出来的图每个节点的出度与入度都为2,所以必然存在欧拉回路。

现在,只需要用问题二中的Fleury算法来求解欧拉路径就可以了。

有下几点需要注意:
1. 有向图也可以用Fleury算法来求解欧拉路径,但是需要将得到的path倒序输出才能得到正确的结果。
2. 实际的程序中不需要真的去构造这样的图,因为所有的边和节点,以及其关系都是已知的。只需要用一个长度为2^N的数组来存储边的状态就可以了(用于Fleury算法的删除边)。
3. 递归的DFS比较消耗栈资源,如果编译器设置的栈空间不够大(一般只有2M),当N比较大(大于12)的时候会发生stackoverflow的错误。为了不爆栈,可以将其改成非递归的算法(我在这折腾了半天,没成功)。Hihocoder的OJ系统的栈空间比较大(据说有1G),所以不会爆栈。

C++代码

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
#include <iostream>
#include <vector>
#include <stack>
#pragma warning(disable:4996)
using namespace std;

int VN;
vector<bool> edges;

void dfs(int n, vector<int> &path) {
int e[2] = { n << 1, (n << 1) + 1 };
for (int i = 0; i < 2; i++) {
if (edges[e[i]]) {
edges[e[i]] = false;
dfs(e[i] & ~VN, path);
}
}
path.push_back(n);
}

int main() {
// freopen("..\\input.txt", "r", stdin);
int N; cin >> N;
if (N == 1) {
cout << "01" << endl;
return 0;
}
VN = 1 << (N - 1);
edges = vector<bool>(VN<<1, true);

vector<int> path;
dfs(0, path);
int len = path.size() - 1;
while (len--) cout << (path[len] & 1);
cout << endl;
}