做网站的语言叫什么,谷歌网站流量统计,免费网站的平台,dw做网站如何让背景变得透明题目解析#xff1a;
输入一些英文单词#xff0c;根据该单词的首尾字母#xff0c;判断所有单词能不能连成一串#xff0c; 类似于成语接龙的意思。同样如果有多个重复的单词时#xff0c;也必须满足这样的条件才能通过#xff0c; 否则都是不可能的情况。输入包括若干…题目解析
输入一些英文单词根据该单词的首尾字母判断所有单词能不能连成一串 类似于成语接龙的意思。同样如果有多个重复的单词时也必须满足这样的条件才能通过 否则都是不可能的情况。输入包括若干个案例每个案例中最多有100000个单词。
题目
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.
思路解析
该题所涉及的知识点主要是并查集和欧拉回路欧拉回路又是什么呢它跟我们 今天所做的“成语接龙”有什么联系呢学过离散的同学都知道欧拉回路是指在图中经 过所有的边一次且仅一次的回路就是欧拉回路。而经过所有的顶点一次且仅一次的回路叫做 哈密顿回路。
现在我们考虑每个单词有用的成分只有首尾字母那么我们把单词的首尾字母 提取出来抽象成两个顶点而恰恰这两个顶点又是有了联系的我们把它们放入一个集合 。实际上无论输入多少个单词首尾字母中所出现的字母无外乎a,b,c……y,z等26个英文字 母。所以反客为主我们不用被动的根据输入的单词来变换首先建立26个集合将有联系 的集合合并merge则矣。当做完这个工作后我们再来看看欧拉回路存在性的判定定理
一、无向图 每个顶点的度数都是偶数则存在欧拉回路。
二、有向图所有边都是单向的 每个节顶点的入度都等于出度则存在欧拉回路。 三.混合图欧拉回路 混合图欧拉回路用的是网络流。
把该图的无向边随便定向计算每个点的入度和出度。如果有某个点出入度之差为奇数那 么肯定不存在欧拉回路。因为欧拉回路要求每点入度 出度也就是总度数为偶数存在 奇数度点必不能有欧拉回路。
AC代码
#includeiostream
#includestring.h
#define inf 0x3f3f3f3f
using namespace std;
int t,m,book[110];
char w[1010];
int dp[110],u[110],v[110];
int gets(int xx)
{if(xxdp[xx])return xx;elsereturn gets(dp[xx]);
}
void dfs(int x,int y)
{int dxgets(x);int dygets(y);if(dx!dy)dp[dy]dx;
}
int main()
{cint;while(t--){for(int i0; i26; i)dp[i]i;cinm;memset(book,0,sizeof(book));memset(u,0,sizeof(u));memset(v,0,sizeof(v));/*care*/for(int i0; im; i){cinw;int lstrlen(w);int aw[0]-a;int bw[l-1]-a;book[a]1;book[b]1;u[a];v[b];dfs(a,b);}int da0,db0;int flag1;for(int i0; i26; i){if(!flag)break;if(!book[i])continue;if(u[i]-v[i]1||u[i]-v[i]-1)flag0;if(u[i]-v[i]1){da;if(da1)flag0;}if(u[i]-v[i]-1){db;if(db1)flag0;}}int ans0;for(int i0; i26; i)if(book[i]dp[i]i){ans;if(ans1){flag0;break;}}if(!flag)coutThe door cannot be opened.endl;elsecoutOrdering is possible.endl;}return 0;
}
