Tag Archives: 欧拉路

hihoCoder week 51-1-欧拉路·三

hihoCoder week 51-1-欧拉路·三
题目1 : 欧拉路·三
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小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串,表示一种符合要求的分布方案
样例输入
3
样例输出
00010111


本题是欧拉路的判定、无向图欧拉路的求解的更进一步,有向图欧拉路的求解。
在有向图中找欧拉路的算法和无向图中相同,还是Fleury算法,只不过这一题需要自己构造有向图。构造的方法详见题目提示,我一开始根据

对于任意两个点,如果点i,点j满足点i的后n-2个数字和点j的前n-2个数字相同,则我们连接有向边(i,j)。

这句话来构造的,略显麻烦。因为

而我们构造的图,由构造方法可以知道对于任意一个点,其入度一定为2,出度一定为2。所以它必定存在欧拉回路。

所以对于每一个点,它有且只有两个出度,我们只需要求出这两个出度即可,不需要0~n-1一个一个点判断。用二进制表示,对于一个特定的点x=a_1a_2...a_n,假设x出边指向的点为y和z,则y,z的前n-1位和x的后n-1位是相同的,也即y=a_2a_3...a_{n-1}0, z=a_2a_3...a_{n-1}1。用公式表示就是y=(x<<1)&(111...1),x左移一位,与上n个1,z=y+1。
把有向图构造好之后,按部就班用Fleury算法求解,再把结果倒序输出,输出的时候只要输出每个点的最后一位就行了。
完整代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxN = 16;
int edge[1 << kMaxN][2];
int path[1 << kMaxN];
int path_size = 0;
int n;
void MakeGraph()
{
	memset(edge, -1, sizeof(edge));
	int nn = 1 << (n - 1);
	for (int i = 0; i < nn; i++)
	{
		edge[i][0] = (i << 1)&(nn - 1);
		edge[i][1] = edge[i][0] + 1;
	}
}
void DFS(int p)
{
	for (int i = 0; i < 2; i++)
	{
		int q = edge[p][i];
		if (q != -1)
		{
			edge[p][i] = -1;
			DFS(q);
		}
	}
	path[path_size++] = p;
}
int main()
{
	scanf("%d", &n);
	if (n == 1)
	{
		printf("01");
		return 0;
	}
	else if (n == 2)
	{
		printf("1100");
		return 0;
	}
	MakeGraph();
	DFS(0);
	while (--path_size)
		printf("%d", path[path_size] & 1);
	return 0;
}

本代码提交AC,用时8MS,内存1MB。

hihoCoder week 50-1-欧拉路·二

hihoCoder week 50-1-欧拉路·二
题目1 : 欧拉路·二
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在上一回中小Hi和小Ho控制着主角收集了分散在各个木桥上的道具,这些道具其实是一块一块骨牌。

主角继续往前走,面前出现了一座石桥,石桥的尽头有一道火焰墙,似乎无法通过。
小Hi注意到在桥头有一张小纸片,于是控制主角捡起了这张纸片,只见上面写着:
将M块骨牌首尾相连放置于石桥的凹糟中,即可关闭火焰墙。切记骨牌需要数字相同才能连接。
——By 无名的冒险者
小Hi和小Ho打开了主角的道具栏,发现主角恰好拥有M快骨牌。
小Ho:也就是说要把所有骨牌都放在凹槽中才能关闭火焰墙,数字相同是什么意思?
小Hi:你看,每一块骨牌两端各有一个数字,大概是只有当数字相同时才可以相连放置,比如:

小Ho:原来如此,那么我们先看看能不能把所有的骨牌连接起来吧。
提示:Fleury算法求欧拉路径
输入
第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"
你可以输出任意一组合法的解。
样例输入
5 5
3 5
3 2
4 2
3 4
5 1
样例输出
1 5 3 4 2 3


上一周学习了怎样判断欧拉通路,这周要给出一条具体的欧拉通路。
欧拉通路的求解使用Fleury算法,其伪代码如下:

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

非常简洁漂亮,本题完整代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxN = 1005,kMaxM=5005;
int n, m,path_size=0;
int path[kMaxM];//是kMaxM而非kMaxN
int edge[kMaxN][kMaxN];
void dfs(int p)
{
	for (int i = 1; i <= n; i++)
	{
		if (edge[p][i]>0)
		{
			edge[p][i]--;
			edge[i][p]--;
			dfs(i);
		}
	}
	path[path_size++] = p;
}
int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	int u, v;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &u, &v);
		edge[u][v]++;//防止有重边
		edge[v][u]++;
	}
	dfs(1);
	for (int i = 0; i < path_size; i++)
		printf("%d ", path[i]);
	return 0;
}

本代码提交AC,用时15MS,内存3MB。需要提醒的是,path的实际大小是m+1,而非n;另外为了防止有重边出现,edge用于记录边的数量,而非是否有边存在。
AC之后我还尝试了先找出欧拉通路的起点,再从起点开始dfs的方法,这种方法并没有更快,因为不论是从哪个点开始dfs,每个点的for循环都要完整执行,所以时间并不会减少,反而会由于寻找起点而增加时间。

hihoCoder week 49-1-欧拉路·一

hihoCoder week 49-1-欧拉路·一
题目1 : 欧拉路·一
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小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”。
样例输入
6 8
1 2
1 4
2 4
2 5
2 3
3 6
4 5
5 6
样例输出
Full


本题考察无向图欧拉路的判断。
关于有向图和无向图欧拉(回)路的介绍,请看POJ Problem 1386: Play on Words。总结一下就是先用并查集判断无向图是否连通,然后判断奇数度的节点个数是否为0或2。完整代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
const int kMax = 10005;
int n, m;
int degree[kMax];
int father[kMax];
int Find(int x)
{
	return x == father[x] ? x : (father[x] = Find(father[x]));
}
void Union(int x, int y)
{
	father[Find(x)] = Find(y);
}
void Init()
{
	for (int i = 1; i <= n; i++)
		father[i] = i;
}
bool IsConnected()
{
	for (int i = 1; i <= n; i++)
		if (father[i] != father[1])
			return false;
	return true;
}
bool IsEuler()
{
	int odd = 0;
	for (int i = 1; i <= n; i++)
		if (degree[i] & 1)
			odd++;
	if (odd == 0 || odd == 2)
		return true;
	return false;
}
int main()
{
	scanf("%d %d", &n, &m);
	int u, v;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &u, &v);
		degree[u]++;
		degree[v]++;
		Union(u, v);
	}
	if (IsConnected())
	{
		if (IsEuler())
			printf("Full\n");
		else
			printf("Part\n");
	}
	else
		printf("Part\n");
	return 0;
}

本代码提交AC,用时13MS,内存1MB。
总结:
判断图中是否存在环路详细介绍可看这里
1. 无向图:依次删除图中度数为0或1的点及其关联的边,循环结束,如果还有未删除的点,则存在回路。
2. 有向图:拓扑排序,依次删除图中入度为0的点及其关联的出边,循环结束,如果还有未删除的点,则存在回路。
判断图是否连通
1. 无向图:使用并查集,最终如果所有节点的父亲都相同,则无向图是连通的。
2. 有向图:判断有向图是否强连通貌似很复杂,Kosaraju算法判断强连通图以及有向图强连通分量的Tarjan算法

POJ 1386-Play on Words

POJ 1386-Play on Words
Play on Words
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 10039 Accepted: 3441
Description
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ``acm'' can be followed by the word ``motorola''. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.
Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".
Sample Input
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
Sample Output
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
Source
Central Europe 1999


给定一系列字符串,问能否将这些字符串依次首尾相连成一个长串,字符串a和b能够相连的条件就是a的最后一个字母和b的第一个字母相同。
这个题目很有意思,像小时候玩的扑克牌游戏“钓鱼”。我一开始想到的是方法是深度优先搜索DFS,在输入的时候将字符串按首字母不同分到不同的队列里面,然后枚举每一个字符串为第一个字符串,进行DFS,如果DFS结束之后遍历了所有字符串,则成功,否则失败。
用枚举+DFS的方法代码如下:

#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int M=26;
int n,used;
vector<vector<string> > s;
//vector<string> rs;//rs内字符串的先后顺序就是这个游戏的先后顺序
bool dfs(string last)
{
	//rs.push_back(last);//记录字符串
	used++;
	if(used==n)
		return true;
	else
	{
		int c=last[last.size()-1]-'a';
		int sz=s.size();
		for(int i=0;i<sz;i++)
		{
			if(dfs(s[i]))
				return true;
			else
				used--;//rs.pop_back();//回溯
		}
		return false;
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int t;
	string tmp;
	cin>>t;
	while(t--)
	{
		cin>>n;
		s.clear();
		s.resize(M);
		for(int i=0;i<n;i++)
		{
			cin>>tmp;
			s[tmp[0]-'a'].push_back(tmp);
		}
		bool success=false;
		for(int i=0;i<M;i++)
		{
			int sz=s[i].size();
			for(int j=0;j<sz;j++)
			{
				used=0;
				success=false;
				if(dfs(s[i][j]))
				{
					success=true;
					break;
				}
			}
			if(success)
				break;
		}
		if(success)
			cout<<"Ordering is possible."<<endl;
		else
			cout<<"The door cannot be opened."<<endl;
	}
	return 0;
}

这一版代码提交MLT,估计是DFS递归栈太深导致的,看来只能想其他办法了。
看了讨论后,发现大多数方法是欧拉路+并查集/DFS。我们先来复习一下欧拉路:
通过图(无向图或有向图)中所有边一次且仅一次,行遍图中所有顶点的通路称为欧拉通路,通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图(Euler Graph),具有欧拉通路而无欧拉回路的图称为半欧拉图。
根据定义,欧拉回路肯定是欧拉通路。相关定理有:
1.无向连通图G是欧拉图,当且仅当G不含奇数度结点(G的所有结点度数为偶数);
2.无向连通图G含有欧拉通路,当且仅当G有零个或两个奇数度的结点;
3.有向连通图D是欧拉图,当且仅当D的基图(即其无向图)为连通图且D中每个结点的入度=出度
4.有向连通图D含有欧拉通路,当且仅当D的基图(即其无向图)为连通图且D中除两个结点外,其余每个结点的入度=出度,且此两点满足deg-(u)-deg+(v)=±1。(起始点s的入度=出度-1,结束点t的出度=入度-1 或两个点的入度=出度)
5.一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环。
6.如果图G是欧拉图且 H = G - uv,则H有奇数个u,v-迹仅在最后访问v;同时,在这一序列的u,v-迹中,不是路径的迹的条数是偶数。(Todia[1973])
以上内容摘自百度百科·欧拉图;关于欧拉路,还可以参考这篇文章。对于本题,我们可以把一个单词的首尾字母看成图的一条边,比如增加"acm"这个单词,则在图上增加一条a->m的有向边。要使所有字符串组成一个首尾相连的长串,等价于在a~z这26个字符串为点构成的图中只存在一条欧拉通路。判断是否存在欧拉通路可以用上面的定理3和4;判断是否只有一条欧拉通路(也就是判断基图是否连通)就需要借助并查集或者DFS,如果用并查集,要保证所有有边的点属于同一个集合;如果用DFS,则从图的某个点出发能遍历到所有右边的点。我使用的是并查集。
理清思路之后就可以开始写代码了,欧拉路+并查集版本的代码如下:

#include<iostream>
#include<string>
using namespace std;
const int M=26;
int n;
int showed[M];//showed[i]表示点i出现过,也就是有边连在i点
int G[M][M];//图
int father[M];//并查集
int degree[M][2];//degree[i][0]入度;degree[i][1]出度
void init_data()
{
	for(int i=0;i<M;i++)
	{
		father[i]=i;
		showed[i]=0;
		degree[i][0]=0;
		degree[i][1]=0;
		for(int j=0;j<M;j++)
			G[i][j]=0;
	}
}
int find_father(int x)
{
	return x==father[x]?x:(father[x]=find_father(father[x]));
}
void union_father(int x,int y)
{
	father[find_father(x)]=find_father(y);
}
//判断有边的点是否属于一个集合
bool is_one_set()
{
	int root=-1;
	for(int i=0;i<M;i++)
	{
		if(showed[i]==1)//有边
		{
			int tmp=find_father(i);
			if(root==-1)
				root=tmp;
			else if(tmp!=root)
				return false;
		}
	}
	return true;
}
bool judge()
{
	if(!is_one_set())
		return false;
	else
	{
		for(int i=0;i<M;i++)
		{
			for(int j=0;j<M;j++)
			{
				if(G[i][j]!=0)
				{
					degree[i][1]+=G[i][j];
					degree[j][0]+=G[i][j];
				}
			}
		}
		int a=0,b=0;//a:入度-出度=-1的个数;b:入度-出度=1的个数
		for(int i=0;i<M;i++)
		{
			int rs=degree[i][0]-degree[i][1];
			if(rs==-1)
				a++;
			else if(rs==1)
				b++;
			else if(rs!=0)
				return false;
		}
		if((a==1&&b==1)||(a==0&&b==0))//欧拉回路或欧拉通路
			return true;
		return false;
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int t,a,b;
	string tmp;
	cin>>t;
	while(t--)
	{
		cin>>n;
		init_data();
		for(int i=0;i<n;i++)
		{
			cin>>tmp;
			a=tmp[0]-'a';
			b=tmp[tmp.size()-1]-'a';
			showed[a]=1;
			showed[b]=1;
			G[a][b]++;//首字母指向尾字母的边
			union_father(a,b);//首字母指向尾字母的边
		}
		if(judge())
			cout<<"Ordering is possible."<<endl;
		else
			cout<<"The door cannot be opened."<<endl;
	}
	return 0;
}

本代码提交AC,用时782MS,内存244K。