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的方法代码如下： [cpp] #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[c].size(); for(int i=0;i<sz;i++) { if(dfs(s[c][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; } [/cpp] 这一版代码提交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，则从图的某个点出发能遍历到所有右边的点。我使用的是并查集。 理清思路之后就可以开始写代码了，欧拉路+并查集版本的代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时782MS，内存244K。]]>