首页 > 代码库 > 【poj1386】 Play on Words
【poj1386】 Play on Words
http://poj.org/problem?id=1386 (题目链接)
题意
给出n个单词,判断它们能否首尾相接的排列在一起。
Solution
将每一格单词的首字母向它的尾字母连一条有向边,那么每一条边就代表一个单词,问题转化为能否不重不漏的走完有向图上所有的边。
连边判是否存在欧拉回路或欧拉路径。
细节
一定要首先判断图的连通性。
代码
// poj1386#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;int r[50],c[50],fa[50];int n,top,cnt;int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]);}int main() { int T;scanf("%d",&T); while (T--) { for (int i=1;i<=26;i++) c[i]=r[i]=0; scanf("%d",&n); char ch[1010]; for (int i=1;i<=26;i++) fa[i]=i; for (int i=1;i<=n;i++) { scanf("%s",ch); int u=ch[0]-‘a‘+1,v=ch[strlen(ch)-1]-‘a‘+1; c[u]++,r[v]++; int r1=find(u),r2=find(v); if (r1!=r2) fa[r1]=r2; } int cnt=0; for (int i=1;i<=26;i++) if ((c[i] || r[i]) && fa[i]==i) cnt++; if (cnt>1) {puts("The door cannot be opened.");continue;} //不连通 cnt=0; for (int i=1;i<=26;i++) { if (abs(c[i]-r[i])==1) cnt++; if (abs(c[i]-r[i])>1) {cnt=3;break;} } if (cnt==1 || cnt>2) {puts("The door cannot be opened.");continue;} //不符合条件 else puts("Ordering is possible."); //正好经过n条边 } return 0;}
【poj1386】 Play on Words
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。