Play on Words
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4142 Accepted Submission(s): 1337
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.
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.".
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.
第一次用深搜做的，提交之后出现 Runtime Error(STACK_OVERFLOW)
然后看到可以使用#pragma comment(linker, "/STACK:102400000,102400000")来解决栈溢出，加了之后然后提交，结果超时了
一下是超时代码：
等我改进。。。。。
/* 超时了、、、、
2013/08/04 16:02
author :zyh
*/
#define N 100003
#include <iostream>
#include <stdio.h>
#include <string.h>
#pragma comment(linker, "/STACK:102400000,102400000")//解决 STACK＿Overflow
using namespace std;
char a[N][3];
char s[1002];
bool visit[N];
int sign,n;
void DFS(int i,int num)
{
if(sign || num == n) return;
// printf("i=%d,num=%d,a=%c\n",i,num,a[i][1]);
visit[i] = 1; num++;
int j,flag = 0;
for(j=0; j<n; j++)
{
if(j!= i && !visit[j] && a[i][1] == a[j][0] ) //找头 和第i行尾相同的
{
// printf("j=%d,a=%c\n",j,a[j][0]);
flag = 1;
DFS(j,num);
}
}
if(!flag && num == n ) //没有找到与末尾相同的，但是是序列最后一个结点
{
sign = 1; return;
}
else {
visit[i] = 0;
return;
}
}
int main()
{
int i,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
gets(s);
a[i][0] = s[0];
a[i][1] = s[strlen(s)-1];
}
// for(i=0;i<n;i++) printf("%d : %c %c\n",i,a[i][0],a[i][1]);
sign = 0;
for(i=0;i<n;i++) visit[i] = 0;
for(i=0;i<n;i++) DFS(i,0);
if(sign) printf("Ordering is possible.\n");
else printf("The door cannot be opened.\n");
}
return 0;
}
欧拉回路
1、欧拉路：在无孤立顶点的图中，若存在一条路，经过图中每条边一次且仅一次，则称此路为欧拉路。如下图（左）中存在一条从顶点1到顶点6的欧拉路。后面的例题（一笔画问题）本质上就是判断一个图是否存在欧拉路。
2、欧拉回路：在无孤立顶点的图中，若存在一条路，经过图中每条边一次且仅一次，且回到原来位置，则称此路为欧拉回路。如下图（右）中任意两个顶点之间都存在欧拉回路。著名的柯尼斯堡七桥问题（图论起源）本质上就是讨论一个图的欧拉回路问题。
3、欧拉图：存在欧拉回路的图，称为欧拉图，图（右）所示的图就是一个欧拉图。
定理1：存在欧拉路的条件：图是连通的，且存在0个或2个奇点。如果存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。
定理2：存在欧拉回路的条件：图是连通的，且不存在奇点。
6、哈密尔顿图：在无孤立顶点的连通图中，若存在一条路，经过图中每个顶点一次且仅一次，则称此图为哈密尔顿图。
7、哈密尔顿环：是一条沿着图的n条边环行的路径，它访问每一个顶点一次且仅一次，并且返回到它的开始位置。
1.首先建立并查集，判断是否是一个根（是否有孤立顶点），首先必须满足一个根结点
2.判断各个点的入度和出度， 入度和出度 都为0 或1，欧拉路
3.中间结点的入度必须等于出度
code：
/*Problem : 1116 ( Play on Words ) Judge Status : Accepted RunId : 8840032 Language : C++ Author : 18236887539 Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta*/
#define N 30
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int father[N],in[N],out[N];
bool visit[N];
int find(int x)
{
while( father[x] != x)
x = father[x];
return x;
}
int main()
{
int i,t,n,a,b;
char s[1002];
scanf("%d",&t);
while(t--)
{
for(i=0;i<N;i++)
{
father[i] = i;
in[i] = out[i] = visit[i] = 0;
}
scanf("%d",&n);
getchar();
while(n--)
{
gets(s);
a = s[0]-'a';
b = s[strlen(s)-1]-'a';
in[b]++;
out[a]++;
father[a] = father[b] = find(a);
visit[a] = visit[b] = 1;
}
int cnt=0;
for(i=0;i<N;i++)
{
if(visit[i] && father[i]==i ) cnt++;
}
if(cnt>1)//根节点个数大于1，不满足
{
printf("The door cannot be opened.\n");
continue;
}
int mid,front,rear;
mid = front = rear = 0;
for(i=0;i<N;i++)
{
if(visit[i] && in[i]!=out[i])//没有存的略过， 入度等于出度的 略过
{
if( out[i]+1 == in[i] ) rear++;
else if(out[i] == in[i]+1) front++;
else mid++;
}
}
// printf("mid=%d,f=%d,r=%d\n",mid,front,rear);
if(mid>0)
{
printf("The door cannot be opened.\n");
continue;
}
if( (front==1&&rear==1) ||( front==0&&rear==0))
{
printf("Ordering is possible.\n");
continue;
}
else printf("The door cannot be opened.\n");
}
return 0;
}