POJ 1386 欧拉路径判断

Description

Input

Output

Sample Input

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

Sample Output

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

先用并查集判断连通，然后再判断节点入度出度是否符合要求。

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/3/26 11:51:38
File Name :12.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int in[100],out[100];
char str[1010];
int fa[30];
int  find(int x){
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
void bin(int x,int y){
	int t1=find(x),t2=find(y);
	if(t1!=t2)fa[t1]=t2;
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int n,T;
	 scanf("%d",&T);
     while(T--){
		 scanf("%d",&n);
		 memset(in,0,sizeof(in));
		 memset(out,0,sizeof(out));
		 for(int i=0;i<26;i++)fa[i]=i;
		 int s=-1;
		 while(n--){
			 scanf("%s",str);
			 int len=strlen(str);
			 int u=str[0]-‘a‘,v=str[len-1]-‘a‘;
			 out[u]++;in[v]++;
			 bin(u,v);
			 if(s==-1)s=u;
		 }
		 int cnt=0,s1=-1,s2=-1,flag=1;
		 for(int i=0;i<26;i++)
			 if(in[i]||out[i]){
				 if(find(s)!=find(i)){
					 flag=0;break;
				 }
				 if(in[i]!=out[i]){
					 if(out[i]-in[i]==1)s1=i;
					 if(out[i]-in[i]==1)s2=i;
					 cnt++;
				 }
			 }
		 if(((cnt==2&&s1!=-1&&s2!=-1)||!cnt)&&flag)flag=1;
		 else flag=0;
		 if(!flag)puts("The door cannot be opened.");
		 else puts("Ordering is possible.");
	 }
     return 0;
}

POJ 1386 欧拉路径判断,布布扣,bubuko.com

POJ 1386 欧拉路径判断

原文：http://blog.csdn.net/xianxingwuguan1/article/details/22165475