HDU 1116 Play on words 欧拉路+并查集

HDU 1116 Play on words 欧拉路+并查集

Problem Description

Play on Words

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5576    Accepted Submission(s): 1831

Problem 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.
具体实现 用 Euler路+并查集来做
先学习欧拉路去 _(:3 [_)_
好啦在看了各个blog的代码之后总算写对啦   一次AC还好
这个题可以抽象出一个图模型  给出这个例子 (图中的数字代表字母 如 1代表 a  2代表 b … 而 (1,2)就代表一个以a开头以b结尾的单词 ,中间部分无用我们忽略即可 )
以26个字母为节点   以单词的首尾字母为边表示链接关系(这里省略了入度和出度都为0的节点)
如何判断可以开门呢,判断的依据就是用上面的方法产生的图是否为Euler图
这样就需要知道什么是Euler图
Euler图有两种
Euler 通路 和Euler回路  这个题是判断有向图是否存在Euler通路或者Euler回路
下面给出Euler通路和回路的判断定理:

②.欧拉路径存在性的判定一。无向图
一个无向图存在欧拉通路,当且仅当   该图所有顶点的度数为偶数   或者  除了两个度数为奇数外其余的全是偶数。

二。有向图
一个有向图存在欧拉通路 当且仅当有且仅有一个节点的出度-入度=1 有且仅有一个节点的入度-出度=1,其余节点入度=出度

有向图存在欧拉回路 当且仅当各个节点的入度=出度

 

因此 我们就可以根据这个来判断是否为欧拉图  分为两步

1.检查图的连通性

2.检查每个节点的出入度数

检查图的连通性我们要用到的算法就是并查集 每次并查集记录这个节点的父节点,父节点就是它的直接or间接后继节点,最终找到BOSS节点 即所有节点的最终根节点 上图中按照下面的算法BOSS节点就是 6

并查集算法如下:

int findroot(int i)									//Search for the connected root of this node
{
	if(father[i]!=i)
	{
		father[i]=findroot(father[i]);
	}
	return father[i];
}

void unionNode(int a,int b)							//Union the two nodes
{
	int x,y;
	x=findroot(a);
	y=findroot(b);
	if(x!=y) father[x]=y;
	return ;
}

 

下面给出Union Find算法执行后的运行的图示

红色的表示最后一次执行后,再次对所有的节点进行UF算法 各个节点的BOSS是谁  可以看出来都是 6

如果不连通肯定不能开门,连通的话就要判断一下度数关系,这时候判断一下Euler通路和回路就好

 

因此 我们主要要存的信息是  每个节点的father  每个节点的度数 每个节点是否被访问过的状态,其余的都是一些标记变量 。下面是AC代码 代码较长,应该有很多地方能够简化

/*************************************************************************
    > File Name: 1116.cpp
    > Author: VOID_133
    > ################### 
    > Mail: ################### 
    > Created Time: 2014年10月23日 星期四 20时55分13秒
	> Comment:并查集&欧拉路  具体见blog
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;

const int maxn=26;
int father[maxn];

int findroot(int i)									//Search for the connected root of this node
{
	if(father[i]!=i)
	{
		father[i]=findroot(father[i]);
	}
	return father[i];
}

void unionNode(int a,int b)							//Union the two nodes
{
	int x,y;
	x=findroot(a);
	y=findroot(b);
	if(x!=y) father[x]=y;
	return ;
}

int main(void)
{
	int in[maxn],out[maxn];							//Keep the indegree and outdegree
	int visit[maxn];
	char word[1005];
	int T;
	int cnt=0;
	bool isEulerLoop;
	bool isEulerPath;
	scanf("%d",&T);
	while(T--)
	{
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
		memset(visit,0,sizeof(visit));
		int n;
		scanf("%d",&n);
		for(int i=0;i<maxn;i++)
		{
			father[i]=i;
		}
		cnt=0;
		while(n--)
		{
			scanf("%s",word);
			int a=word[0]-'a';
			int b=word[strlen(word)-1]-'a';
			visit[a]=visit[b]=1;
			unionNode(a,b);
			out[a]++;
			in[b]++;
		}
		for(int i=0;i<maxn;i++)
		{
			father[i]=findroot(i);								//Find the roots 
		}
		/*//DEBUG
		printf("nDEBUG FATHERSn");
		for(int i=0;i<maxn;i++)
		{
			printf("father[%d]=%dn",i,father[i]);
		}
		printf("nDEBUG INn");
		for(int i=0;i<maxn;i++)
		{
			printf("in[%d]=%dn",i,in[i]);
		}
		printf("nDEBUG OUTn");
		for(int i=0;i<maxn;i++)
		{
			printf("out[%d]=%dn",i,out[i]);
		}
		//END DEBUG*/
		for(int i=0;i<maxn;i++)								//How to judge it only has one root
		{
			if(father[i]==i && visit[i])
				cnt++;
		}
		if(cnt!=1)
		{
			printf("The door cannot be opened.n");
		}
		else
		{
			isEulerLoop=true;
			isEulerPath=true;
			for(int i=0;i<maxn;i++)
			{
				if(in[i]!=out[i]) 
				{
					isEulerLoop=false;
				}
			}
			if(!isEulerLoop)
			{
				//Judge if it's Euler Path;
				int flaga=0;
				int flagb=0;
				for(int i=0;i<maxn;i++)
				{
					if(in[i]!=out[i])
					{
						if(in[i]-out[i]==1) flaga++;
						else if(out[i]-in[i]==1) flagb++;
						else
						{
							isEulerPath=false;
							break;
						}
					}
				}
				if(flaga!=1 || flagb!=1) isEulerPath=false;
			}
			if(isEulerLoop)
			{
				printf("Ordering is possible.n");
			}
			else if(isEulerPath)
			{
				printf("Ordering is possible.n");
			}
			else
			{
				printf("The door cannot be opened.n");
			}
		}
	}
	return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

19 − four =

This site uses Akismet to reduce spam. Learn how your comment data is processed.