【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;

}