AcWing1185 单词游戏（欧拉路径）

基本建图套路，从单词头向单词尾连一条边，答案就是是否存在一条欧拉路径

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int p[N];
int din[N],dout[N];
int st[N];
int find(int x){
    if(x!=p[x]){
        p[x]=find(p[x]);
    }
    return p[x];
}
int g[50][50];
int main(){
    int n,t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int i;
        memset(st,0,sizeof st);
        memset(din,0,sizeof din);
        memset(dout,0,sizeof dout);
        for(i=0;i<=n;i++){
            p[i]=i;
        }
        for(i=1;i<=n;i++){
            string s;
            cin>>s;
            int a=s[0]-'a',b=s[(int)s.size()-1]-'a';
            st[a]=st[b]=1;
            g[a][b]++;
            dout[a]++,din[b]++;
            int pa=find(a),pb=find(b);
            p[pa]=pb;
        }
        int sign=-1;
        int res=0;
        for(i=0;i<26;i++){
            if(st[i]){
                if(sign==-1)
                sign=find(i);
                else{
                    if(sign!=find(i)){
                        res=1;
                        break;
                    }
                }
            }
        }
        int start=0,ed=0;
        for(i=0;i<26;i++){
            if(din[i]!=dout[i]){
                if(dout[i]==din[i]+1)
                    start++;
                else if(din[i]-1==dout[i])
                    ed++;
                else{
                    res=1;
                    break;
                }
            }
        }
        if(start!=0||ed!=0){
            if(start!=1||ed!=1)
            res=1;
        }
        if(res==1){
            cout<<"The door cannot be opened."<<endl;
        }
        else{
            cout<<"Ordering is possible."<<endl;
        }
    }
}