Play on Words 单词 UVA 10129 (欧拉+dfs)

淩亂°似流年 2024-02-17 18:56 26阅读 0赞

概念：无向图中

欧拉道路（也叫欧拉通路），需要满足的条件图是连通的并且最多只有两个奇顶点（这两个奇顶点是欧拉通路的端点）；欧拉回路：图是连通的并且没有奇顶点。

有向图中也相似：

欧拉道路：图是连通的并且除两个顶 点外所有的点的出度等于入度 并且这两个顶点中 一个是出度多1，一个是入度多1；欧拉回路：图是连通的并且所有的顶点的出度等于入度。

解题思路：把单词首、尾看做顶点，中间看做带有方向的边，问题就转换成了判断有向图是否存在欧拉道路问题了（刚开始一直没搞懂为什么可以转换为欧拉道路求解，题目是判断是否存在一个首尾相接的序列，，，不负苦心人 终于还是弄懂了（欧拉道路就是访问所有的边仅一次，拉直了就是一个首尾相接的序列啦）） 。欧拉 + DFS求解：

代码如下：

1.  \#include<cstdio>
2.  \#include<cstring>
3.  const int len=26+10;
4.  int indeg\[len\],outdeg\[len\],G\[len\]\[len\],visit\[len\]; //入度、出度、点是否在图中出现过、是否被访问过
5.  void dfs(int u)\{ 
6.   visit\[u\]=1;
7.   for(int v=0;v<26;v++)\{ 
8.   if(G\[u\]\[v\] && !visit\[v\])dfs(v);
9.   \}
10. \}
11. int main()\{ 
12.  int T;
13.  scanf("%d",&T);
14.  while(T--)\{ 
15.  memset(indeg,0,sizeof(indeg));
16.  memset(outdeg,0,sizeof(outdeg));
17.  memset(G,0,sizeof(G));
18.  memset(visit,0,sizeof(visit));
19.  int N;
20.  scanf("%d",&N);
21.  for(int i=0;i<N;i++)\{ 
22.  char s\[1000+10\];
23.  scanf("%s",s);
24.  int len1=strlen(s);
25.  G\[s\[0\]-'a'\]\[s\[len1-1\]-'a'\]=1;
26.  \++outdeg\[s\[0\]-'a'\];
27.  \++indeg\[s\[len1-1\]-'a'\];
28.  \}
29.   
    
30.  bool flag=true;
31.  int num1=0,num2=0;
32.  for(int i=0;i<26;i++)\{ 
33.  if(indeg\[i\]!=outdeg\[i\])\{ 
34.  if(indeg\[i\]==outdeg\[i\]+1)num2++;
35.  else if(outdeg\[i\]==indeg\[i\]+1)num1++;
36.  else \{ 
37.  flag=false;break;
38.  \}
39.  \}
40.  \}
41.  if(num1>1 ||num2>1 || num1!=num2)flag=false; //num1、num2的个数要么都为0，要么都是1
42.  bool flag2=true;
43.  if(flag)
44.  \{for(int i=0;i<26;i++)
45.  if(outdeg\[i\])
46.  \{dfs(i); break; \} //找一个点进行dfs 
47.   
    
48.  for(int i=0;i<26;i++)
49.  if(indeg\[i\] || outdeg\[i\])
50.  if(!visit\[i\])\{ 
51.  flag2=false;
52.  break;
53.  \}
54.  \}
55.  if(flag && flag2)printf("Ordering is possible.\\n");
56.  else printf("The door cannot be opened.\\n");
57.  \}
58.  return 0;
59. \}