HDU 1116 && POJ 1386 Play on Words(欧拉路径)

按字母来建边，每个单词的首字母和尾字母加边。先判断是否连通，然后判断每个字母的入度和出度不能出现差的绝对值大于2，然后入度和出度差的绝对值为1的不能超过两个。就可以形成欧拉路径

代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=100000+10;
char s[1100];
int in[30], out[30], bin[30], _hash[30], f[30], vis[30];
int find1(int x)
{
        return bin[x]==x?x:bin[x]=find1(bin[x]);
}
void join(int x, int y)
{
        int f1=find1(bin[x]);
        int f2=find1(bin[y]);
        if(f1!=f2){
                bin[f2]=f1;
        }
}
void init()
{
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(_hash,0,sizeof(_hash));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<25;i++){
                bin[i]=i;
        }
}
int main()
{
        int t, n, i, len, sum, cnt, x;
        scanf("%d",&t);
        while(t--){
                scanf("%d",&n);
                init();
                cnt=0;
                for(i=0;i<n;i++){
                        scanf("%s",s);
                        len=strlen(s);
                        in[s[len-1]-'a']++;
                        out[s[0]-'a']++;
                        join(s[0]-'a',s[len-1]-'a');
                        vis[s[0]-'a']=vis[s[len-1]-'a']=1;
                }
                for(i=0;i<25;i++){
                        if(!vis[i]) continue ;
                        x=find1(bin[i]);
                        if(!_hash[x]){
                                        _hash[x]=1;
                                        cnt++;
                                }
                }
                if(cnt>1) puts("The door cannot be opened.");
                else{
                        sum=0;
                        bool flag=0;
                        for(i=0;i<25;i++){
                                if(abs(in[i]-out[i])==1){
                                        sum++;
                                }
                                else if(abs(in[i]-out[i])>1){
                                flag=1;
                                }
                        }
                        if(sum>2||flag) puts("The door cannot be opened.");
                        else puts("Ordering is possible.");
                }
        }
        return 0;
}