大家伙都用并查集，我就用下欧拉路径的 dfs 来判断连通性吧

这题类似：spoj2885 单词环

算法分析：

• 把单词看成一条边，每输入一个单词看成从首字母到尾字母的一条边。这样我们就能通过欧拉路径的分析方法判断是否存在从一个点出发连接所有边的路径（即欧拉路径），注意：这里不一定是回路，能连接所有单词即可
• 因为是有向边开两个度数数组，din和dout，欧拉路径除了终点和起点外要求其他每个点入度=出度，判断每个点的入度不等于出度有三种可能：起点、终点、不存在欧拉路径。
• 值得注意的是如果这些边中度数已经不满足要求，即起点或终点个数不止一个，或起点数!=终点数的时候都是属于不存在欧拉路径的情况。因此要先判断，再dfs。因为dfs在要保证正确性的前提下只能判断是否连通，即最后 cnt == m ? 连通 : 不连通。因为不存在欧拉路径时亦可能 cnt = m，

总结：欧拉路径除了连通性都用din和dout数组来判断，连通性用dfs来判断。

#include <bits/stdc++.h>
using namespace std;

const int N = 1010,M=100010;

int e[M],ne[M],h[N],idx;
int n,m;
int din[N],dout[N];
int cnt;

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    for(int &i=h[u];~i;)
    {
        int j=e[i];
        i=ne[i];
        dfs(j);

        cnt++;
    }
}

int main()
{
    char str[N];
    int T; cin>>T;
    while(T--)
    {
        memset(h, -1, sizeof h);
        idx=cnt=0;
        memset(din,0,sizeof din);
        memset(dout,0,sizeof dout);
        cin>>m;
        for(int i=0;i<m;i++)
        {
            scanf("%s",str);
            int a=str[0]-'a', b=str[strlen(str)-1]-'a';
            add(a,b);
            din[b]++, dout[a]++;
        }

        int start=0,s=0,e=0;
        while(din[start]+dout[start]==0) start++; //防止是回路的情况
        for(int i=start;i<26;i++)
            if(din[i]!=dout[i])
            {
                if(dout[i]==din[i]+1) //存在一个起点
                {
                    start=i;
                    s++;
                }
                else if(din[i]==dout[i]+1) e++; //存在一个终点
                else
                {
                    s=10000;
                    break;
                }
            }

        if(s>1||e>1||s!=e) //不存在欧拉路径
        {
            puts("The door cannot be opened.");
            continue;
        }

        dfs(start);

        if(cnt<m) puts("The door cannot be opened.");
        else puts("Ordering is possible.");
    }

    return 0;
}