HDU 1116 Play on Words 有向欧拉图

本文借鉴大神博客
欧拉环与欧拉路径的判断求法

定义：一个有向图是半欧拉图当且仅当该图的基图是连通的且有且只有一个点的入度比出度少1（作为欧拉路径的起点），有且只有一个点的入度比出度多1（作为终点），其余点的入度等于出度。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define CLR(x) memset(x,0,sizeof(x))
#define maxn 30
#define longest 1010
using namespace std;

int T,N;
int Father[maxn];
int vis[maxn],out[maxn],in[maxn];             //存储入度点与出度点
int len,sta,fin;                              //字符串长度，起点，终点
int innum, outnum,root;                       //存储总入度与出度值
char str[longest];

int Find(int x)
{
    if(Father[x] == x) return x;
    else return Find(Father[x]);
}

void Union(int a, int b)
{
    int A = Find(a), B = Find(b);
    if(A != B) Father[B] = A;
}

void ini()                                          //初始化
{
    for(int i=0; i<maxn; i++)
    {
        Father[i] = i;
    }
    CLR(vis);CLR(out);CLR(in);
    innum=0,outnum=0,root=0;
}


int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N)；
        ini();
        for(int i=0; i<N; i++)
        {
            scanf("%s",str);
            len = strlen(str);
            sta = str[0]-'a'+1; fin = str[len-1]-'a'+1;
            vis[sta] = 1,vis[fin] = 1;
            out[sta]++, in[fin]++;
            Union(sta,fin);                                     //构建联通图
        }
        int flag=1,flag1=1;
        for(int i=1; i<maxn; ++i)
        {
            if(vis[i])
            {
                if(Father[i] == i) root++;                                //判断连通分量
                if(in[i] != out[i])
                {
                    if(in[i] - out[i] == 1) innum++;                      //找到有向半欧拉图的起点
                    else if(out[i] - in[i] == 1) outnum++;                //找到有向半欧拉图的终点
                    else flag1 = 0;
                }
            }
            if(root > 1){flag = 0;break;}                                 //有不连通部分
        }
        if((flag && innum == 0 && outnum == 0 && flag1/*有向欧拉环*/) || (flag && innum == 1 && outnum == 1 && flag1/*有向半欧拉图*/))
            printf("Ordering is possible.\n");
        else
            printf("The door cannot be opened.\n");
    }
    return 0;
}