poj 1386 Play on Words(有向图欧拉回路)

简介:
1 /*
 2   题意:单词拼接,前一个单词的末尾字母和后一个单词的开头字母相同
 3   思路:将一个单词的开头和末尾单词分别做两个点并建一条有向边!然后判断是否存在欧拉回路或者欧拉路 
 4 
 5   再次强调有向图欧拉路或欧拉回路的判定方法:
 6 (1)有向图G为欧拉图(存在欧拉回路),当且仅当G的基图连通,且所有顶点的入度等于出度。
 7 (2)有向图G为半欧拉图(存在欧拉道路),当且仅当G的基图连通,且存在顶点u的入度比出度大1、v的入度比出度小1,
 8    其它所有顶点的入度等于出度(顶点u,v的个数必须都是1)。
 9    
10    求该图的连通性的时候,只要求该有向图是弱连通的就可以了!所以转换为无向图的连通问题! 
11 */ 
12 #include<iostream>
13 #include<cstring>
14 #include<cstdio>
15 #include<algorithm>
16 using namespace std;
17 
18 int g[30][30];
19 char ch[1005];
20 int vis[30], used[30];
21 int inD[30], outD[30];
22 
23 void dfs(int u){
24    vis[u]=1;
25    for(int i=0; i<26; ++i)
26       if(g[u][i] && !vis[i])
27          dfs(i);
28 } 
29 
30 bool checkDeg(){
31     int inOut=0, outIn=0;
32     for(int i=0; i<26; ++i)
33        if(used[i] && inD[i]-outD[i]!=0){
34           if(inD[i]-outD[i]>1 || inD[i]-outD[i]<-1) return false;
35           else inD[i]-outD[i]>0 ? ++inOut : ++outIn; 
36        }
37     return (inOut==1 && outIn==1) || (inOut==0 && outIn==0);
38 }
39 
40 int main(){
41     int n, t;
42     scanf("%d", &t);
43     while(t--){
44         scanf("%d", &n);
45         memset(vis, 0, sizeof(vis));
46         memset(used, 0, sizeof(used));
47         memset(g, 0, sizeof(g));
48         memset(inD, 0, sizeof(inD));
49         memset(outD, 0, sizeof(outD)); 
50         while(n--){
51            scanf("%s", ch);
52            int u=ch[0]-'a', v=ch[strlen(ch)-1]-'a';
53            g[u][v]=g[v][u]=1;//无向图的连通性 即是有向图的弱连通 
54            used[u]=used[v]=1;
55            ++inD[v];
56            ++outD[u];
57         }
58         bool flag=true;
59         for(int i=0; i<26; ++i)
60            if(used[i]){
61               dfs(i);
62               break;
63            }
64         for(int i=0; i<26; ++i)
65            if(used[i] && !vis[i]){
66               flag=false;
67               break;
68            }
69         if(flag && !checkDeg())
70            flag=false;
71         if(flag)
72            printf("Ordering is possible.\n"); 
73         else printf("The door cannot be opened.\n");
74     }
75     return 0;
76 } 
复制代码









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3921728.html,如需转载请自行联系原作者
目录
相关文章
|
存储 容器
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
138 0
|
SQL Shell
HDU-4348 To the moon(主席树区间修改 永久化标记)
HDU-4348 To the moon(主席树区间修改 永久化标记)
141 0
HDU-4348 To the moon(主席树区间修改 永久化标记)
UPC Graph (最小生成树 || 并查集+二分)
UPC Graph (最小生成树 || 并查集+二分)
92 0
POJ-2251,Dungeon Master(三维迷宫BFS)
POJ-2251,Dungeon Master(三维迷宫BFS)
|
C语言
HDOJ/HDU Tempter of the Bone(深搜+奇偶性剪枝)
HDOJ/HDU Tempter of the Bone(深搜+奇偶性剪枝)
97 0