HDU——1116 Play on words

题目大意

这个题让我们求给出的几个字符串是否能全部首尾相连，字符串长度至少为2，其连接方式类似于成语接龙，需要一个字符串的尾巴与第二个字符串开头相同。

样例输入

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

样例输出

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

题目分析

这题是个欧拉回路和并查集的结合。因为我是菜鸟还不是很懂欧拉回路就不在此赘述，日后理解后再详细写。
先说说我的想法：
1.将每个输入的字符串的首字母与尾字母的入度和出度分别加一，分别放在in[]与out[]数组中。并记录出现过的字母（只记录首位）。

2.判定其是否满足题目所给的条件相连即只有一个字母入度减出度为1，一个字母入度减出度为-1，剩下的入度减去出度都为0。若不满足直接退出。

3.剩下的就判断其是否有连通性，我使用并查集的时候将father数组的根节点位置记录为他节点的个数并以负数表示。然后每输入一个字符串将首尾字母合并，而若是首尾字母相同，则不合并。这样若形成的是链而不是环的话，father数组中最小的值（因为是负数）就与输入的字符串首尾字母出现的个数相同。
若相同则判断可行，反之不行。

（好吧可能我的叙述方式有点问题，还是把代码贴出来，讲道理代码也丑）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int pre[30];
int in[30],out[30],n,ans[30];// ans用来记录in与out相减的值。
char word[1010];
int judge[30];  //判断字母是否出现过，出现过为1，否则为0。

int Find(int x)
{
    if(pre[x] < 0) return x;
    return pre[x] = Find(pre[x]);
}

int Union(int R1 , int R2)
{
    int r1 = Find(R1) , r2 = Find(R2);
    int temp = pre[r1] + pre[r2];
    if(pre[r1] > pre[r2])
    {
        pre[r1] = r2; pre[r2] = temp;
    }
    else
    {
        pre[r2] = r1 ; pre[r1] = temp;
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(word,0,sizeof(word));
        memset(judge,0,sizeof(judge));
        memset(pre,-1,sizeof(pre));
        scanf("%d",&n);
        for(int i = 1 ; i <= n ;i++)
        {
            scanf("%s",word);
            int len = strlen(word);
            judge[word[0]-'a'+1]=1 ;
            judge[word[len-1]-'a'+1]=1;//将首尾字母记录为出现过。

            in[word[0]-'a'+1]++;
            out[word[len-1]-'a'+1]++;
            if(Find(word[0]-'a'+1) != Find(word[len-1]-'a'+1))
            {
                Union(word[0]-'a'+1,word[len-1]-'a'+1);   //若首尾字母不同则合并。
            }
        }
        for(int i = 0 ; i < 30 ; i++)
        {
            ans[i] = in[i] - out[i];         //将所有字母入度和出度的值记录下来。
        }
        int co1 = 0 , co2 = 0 , flag = 1;
        for(int i = 0 ; i < 30 ; i++)        //从这里开始判断是否只有一个-1，一个1，其余全为0的情况。
        {
            if(ans[i]!=0&&ans[i]!=-1&&ans[i]!=1)
            {
                flag = 0;
                break;
            }
            if(ans[i]==-1)
            {
                co1++;
                if(co1 > 1)
                {
                    flag = 0;
                    break;
                }
            }
            if(ans[i]==1)
            {
                co2++;
                if(co2>1)
                {
                    flag = 0; break;
                }
            }
        }
        if(flag == 0)                          //不满足则退出
        {
            printf("The door cannot be opened.\n"); continue;
        }
        int con = 0;
        for(int i = 0 ; i < 30  ; i++)          //记录出现过字母的个数 。
        {
            if(judge[i]) con++;
        }
        flag = 0;
        for(int i = 0 ; i < 30 ; i++)            //判断与最长链的节点个数是否相等。
        {
             if(pre[i]==(-1)*con)
             {
                 flag = 1;break;
             }
        }
        if(flag == 1) printf("Ordering is possible.\n");
        else printf("The door cannot be opened.\n");


    }
}