首页 > 代码库 > 【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