HDU 1116 Plays on words

只能说自己渣爆了

一开始写了一个递归函数，用深搜的方法去遍历所有可能的，但是最后一直stackoverflow，加了一个扩大栈的语句还是无动于衷

最后发现自己写的那个递归就是欧拉回路算法···

后来看了一下，都是说欧拉回路，没仔细想。早上起来想了一下，好像可以建一个图，然后搜索···这个搜索就是一条欧拉（回）路

1.如果是一条链，是路，否则是回路

2.欧拉图有其特性，如果用搜索做，数据量很大，容易栈溢出或超时（5s应该不至于吧）

3.并查集用来检测是否只有一个连通分量而已。

#include <queue>
#include <stdio.h>

int a , b , u , v , fa[26] , ans[26] , vis[26];
int out[26] , in[26];

int find(int x) { return x==fa[x] ? x : fa[x] = find(fa[x]);}

void union_set(int a,int b){
    u = find(a) ; v = find(b);
    if(u != v) fa[u] = v;
}

int main(){
    int T,n,cnt,larin,larout,len,nodes;
    char s[1010];
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<26;i++) fa[i] = i , vis[i] = 0 ,in[i]=out[i]=0;
        while(n--){
            scanf("%s",s);
            len = strlen(s);
            a = s[0] - 'a', b = s[len-1] - 'a';
            vis[a] = vis[b] = 1;
            out[a] ++;
            in[b] ++;
            union_set(a,b);
        }
        // not a set?
        cnt = 0;
        for(int i=0;i<26;i++) {
            if(!vis[i]) continue;
            if(fa[i] == i) cnt++;
        }
        int sum = 0;
        larin = larout = nodes = 0;
        for(int i=0;i<26;i++){
            if(!vis[i]) continue;
            ans[i] = in[i] - out[i];
            //nodes += (ans[i] == 0 ? 1 : 0);
            if(ans[i] == 1) larin ++;
            if(ans[i] == -1) larout++;
            if(ans[i] == 0) nodes ++;
            sum ++;
        }
        if(cnt > 1){
            puts("The door cannot be opened.");
            continue;
        }
        if((larin==1&&larout==1&&nodes==sum-2) ||
            (nodes == sum)){
                puts("Ordering is possible.");
        }
        else puts("The door cannot be opened.");
    }
    return 0;
}