hihocoder 1181 欧拉路·二 Fleury算法

缘起

【1】中我们介绍了无向图的欧拉回路的求法. 其实我要告诉大家, 【1】中的算法就是 fleury 算法.

hihocoder 1181 欧拉路·二

分析

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

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

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

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

1
2
将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”

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

样例输入

1
2
3
4
5
6
5 5
3 5
3 2
4 2
3 4
5 1

样例输出

1
1 5 3 4 2 3

从题意上来讲，显然是将所有数字看做图中的顶点，然后求该无向图中的欧拉路径（可能是欧拉环路）.

求无向图的欧拉路径的算法有一种叫做 fleury 的算法. 该算法的伪代码是

1
2
3
4
5
6
7
8
9
DFS(u)
{
	While (u存在未被删除的边e(u,v))
	{	
		删除边e(u,v); // 使得只能沿着主干道路进行, 不会再回到圈中, 即dfs消圈（【1】）
		DFS(v); // 走完圈
	}
	Path[PathSize++] = u;
}

那么上述fleury算法的原理是什么呢? 我们知道，有欧拉环路的无向图的欧拉环路其实是由一条起点和终点可能不同的边不重复的路径（下称主干道路）+若干圈构成的（【1】中说过）. 就像下面这个样子

对于上面的无向图——欧拉路径的走法是显然的——每次走过去的时候，遇到圈就先把圈走完，再继续沿着主干道路行进即可.

所以不难写下如下ac代码（如果不懂，可以参见【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
56
57
58
59
60
61
62
63
64
65
66
67
//#include "stdafx.h"
#include <stdio.h>
#include <vector>
using namespace std;
//#define LOCAL
typedef pair<int, int> P; // first是点的编号, second是边的编号
typedef vector<P>::iterator vit;

int n,m,deg[1005],start,ans[5005],top; // start是欧拉回路的起点
vector<P> g[1005];
struct
{
	int x,y; // 两端数字为x和y的骨牌
	bool v;
}bb[5005]; // 骨牌

void dfs(int i)
{
	for (vit x = g[i].begin(); x!=g[i].end(); x++)
	{
		if (!bb[x->second].v) // 如果此边没走过
		{
			bb[x->second].v = true;
			dfs(x->first); // 消圈
			ans[top++] = x->second;
		}
	}
}

int main()
{	
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d%d", &n, &m);
	for (int i = 1;i<=m;i++) // 给边编号1,...,m
	{
		scanf("%d%d", &bb[i].x, &bb[i].y);
		g[bb[i].x].push_back(P(bb[i].y,i)); // x和y通过边i连接
		g[bb[i].y].push_back(P(bb[i].x,i)); // 无向图
		deg[bb[i].x]++, deg[bb[i].y]++;
	} // 本题比【1】简单, 因为【1】还要字典序最小,本题任取一种即可,所以不需要排序
	for (int i = 1; i<=n; i++)
	{
		if (deg[i] &1)
		{
			start = i;
			break; // 注意, 本题输入保证存在欧拉回路
		}
	}
	if (!start)
	{
		start = 1;
	} // 如果所有顶点都是偶度点的话, 任取起点,这里取1
	dfs(start); // 跑fleury算法, 最后ans中保存的就是骨牌的排放顺序
	for (int i = top-1;~i; i--) // 逆序输出边
	{
		printf("%d",start);
		start = bb[ans[i]].x+bb[ans[i]].y-start;
		if (i)
		{
			putchar(' ');
		}
	}
	printf(" %d",start);
	return 0;
}

ac情况（没错，hihocoder的结果就是这么简明~）

结果:Accepted

参考

【1】https://yfsyfs.github.io/2019/09/06/poj-1041-John-s-trip-%E6%97%A0%E5%90%91%E5%9B%BE%E6%B1%82%E6%AC%A7%E6%8B%89%E5%9B%9E%E8%B7%AF%E6%A8%A1%E6%9D%BF/