学步园

题目链接：Click here~~

题意：

给 n 个词语，问是否能够词语接龙。

解题思路：

先用并查集找连通分量，然后根据结论来吧。

#include <map>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

namespace UFset
{
    const int N = 27;
    int pre[N];
    void init(){
        memset(pre,-1,sizeof(pre));
    }
    int root(int x){
        return pre[x] == -1 ? x : pre[x] = root(pre[x]);
    }
    bool gather(int a,int b){
        int r1 = root(a);
        int r2 = root(b);
        if(r1 == r2)
            return false;
        else
            pre[r1] = r2;
            return true;
    }
}

using namespace UFset;

int ind[N],outd[N];

bool EulerTour(int n)       //direct
{
    int rt = -1;
    for(int i=1;i<=n;i++)
        if(ind[i] || outd[i])
        {
            if(rt == -1)
                rt = root(i);
            else if(rt != root(i))
                return false;
        }
    vector<int> tmp;
    for(int i=1;i<=n;i++)
        if(ind[i] != outd[i])
            tmp.push_back(outd[i]-ind[i]);
    return (int)tmp.size() == 0 || (int)tmp.size() == 2 && tmp[0] * tmp[1] == -1;
}

char word[1005];

int main()
{
    int n = 26,m,T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d",&m);
        memset(ind,0,sizeof(ind));
        memset(outd,0,sizeof(outd));
        for(int i=0;i<m;i++)
        {
            scanf("%s",word);
            int u = word[0] - 'a' + 1;
            int v = word[strlen(word)-1] - 'a' + 1;
            gather(u,v);
            ++outd[u] , ++ind[v];
        }
        puts(EulerTour(n)?"Ordering is possible.":"The door cannot be opened.");
    }
    return 0;
}