首页 > 代码库 > POJ--1386--Play on Words【判断有向图欧拉通路、欧拉回路】
POJ--1386--Play on Words【判断有向图欧拉通路、欧拉回路】
链接:http://poj.org/problem?id=1386
题意:要开启一扇门,n个单词是密码,n个单词中,如果一个单词的首字母和前一个单词的尾字母相同,并且每个单词都能这么连起来且只用一次,则门可以开启,否则不能开启,现给出单词,判断门是否可以开。
有向图欧拉通路充要条件:D为有向图,D的基图连通,并且所有顶点的出度与入度都相等;或者除两个顶点外,其余顶点的出度与入度都相等,而这两个顶点中一个顶点的出度与入度之差为1,另一个顶点的出度与入度之差为-1。
有向图欧拉回路充要条件:当D的所有顶点的出、入度都相等时,D中存在有向欧拉回路。
思路:一个单词关键是首字母和尾字母,可以把首字母和尾字母看成顶点,这个单词看成这两个顶点间的边,这么建图,于是原题就变成了找这个图中是否存在欧拉通路或者欧拉回路。建完图之后只需要根据定理判断每个顶点的出度、入度以及图的连通性即可。
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 500100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define mod 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int du[30],vis[30],father[30]; int n,cnt; char str[1010]; int Find(int x){ int t = x; while(t!=father[t]) t = father[t]; int k = x; while(k!=t){ int temp = father[k]; father[k] = t; k = temp; } return t; } int main(){ int t,i,j,l; scanf("%d",&t); while(t--){ cnt = 0; memset(du,0,sizeof(du)); memset(vis,0,sizeof(vis)); for(i=0;i<30;i++) father[i] = i; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%s",str); l = strlen(str); du[str[0]-'a']--; du[str[l-1]-'a']++; vis[str[0]-'a'] = 1; vis[str[l-1]-'a'] = 1; int aa = Find(str[0]-'a'); int bb = Find(str[l-1]-'a'); if(aa!=bb){ if(aa<bb) father[bb] = aa; else father[aa] = bb; } } int flag1,flag2,flag3,flag; flag1 = flag2 = flag3 = flag = 0; for(i=0;i<30;i++){ if(du[i]==0) continue; else if(du[i]==-1) flag1++; else if(du[i]==1) flag2++; else flag3 = 1; } if(!flag3&&flag1==1&&flag2==1) flag = 1; else if(!flag1&&!flag2&&!flag3) flag = 1; else flag = 0; if(flag){ int tt = 0; for(i=0;i<26;i++){ if(vis[i]&&father[i]==i){ tt++; } } if(tt>1) flag = 0; if(flag) puts("Ordering is possible."); else puts("The door cannot be opened."); } else puts("The door cannot be opened."); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。