题目大意
这个题让我们求给出的几个字符串是否能全部首尾相连，字符串长度至少为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");
}
}
