c++ Union Find判Euler Path

#include <iostream>
#include <cstring>

using namespace std;

const int N=30; // 26个字母的顶点
int din[N], dout[N]; // 顶点的出度和入度
bool vis[N]; // 记录使用到的字母
int fa[N]; // union find set
int T, n;

inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
inline void init(){for(int i=0; i<26; ++i) fa[i]=i;}

int main(){
    string word;
    cin>>T;
    while(T--){
        cin>>n;
        memset(din, 0x00, sizeof din);
        memset(dout, 0x00, sizeof dout);
        memset(vis, 0x00, sizeof vis);
        init();
        for(int i=0; i<n; ++i){
            cin>>word;
            int x=word[0]-'a';
            int y=word.back()-'a';
            vis[x]=vis[y]=true;
            // 建立一条由x指向y的有向边
            dout[x]++;
            din[y]++;
            // 设置在同一个连通分量中
            fa[find(x)]=find(y);
        }

        // 判断度数
        int s=0, e=0;
        bool ok=true;
        for(int i=0; i<26; ++i)
            if(din[i]!=dout[i]){
                if(din[i]==dout[i]+1) ++e;
                else if(din[i]+1==dout[i]) ++s;
                else {ok=false; break;}
            }
        // 有向图Euler path判定
        // 或者起点和终点数量都是0(形成环)
        // 或者起点和终点数量都是1
        if(!(!s&&!e||s==1 && e==1)) ok=false;

        // 判断连通性
        int fv=-1;
        for(int i=0; i<26; ++i){
            if(vis[i]){
                if(fv==-1) fv=find(i);
                else if(fv!=find(i)){ok=false; break;}
            }
        }

        if(ok) cout<<"Ordering is possible."<<endl;
        else cout<<"The door cannot be opened."<<endl;
    }

    return 0;
}

c++ DFS判Euler Path

#include <iostream>
#include <cstring>

using namespace std;

const int N=30; // 26个字母的顶点
int din[N], dout[N]; // 顶点的出度和入度
int g[N][N];
int T, n, cnt;

void dfs(int u){
    for(int i=0; i<26; ++i){
        if(g[u][i]){
            ++cnt;
            --g[u][i];
            dfs(i);
        }
    }
}

int main(){
    string word;
    cin>>T;
    while(T--){
        cnt=0;
        cin>>n;
        memset(din, 0x00, sizeof din);
        memset(dout, 0x00, sizeof dout);
        memset(g, 0x00, sizeof g);
        for(int i=0; i<n; ++i){
            cin>>word;
            int x=word[0]-'a';
            int y=word.back()-'a';
            // 建立一条由x指向y的有向边
            dout[x]++;
            din[y]++;
            g[x][y]++;
        }

        // 判断度数
        int s=0, e=0;
        bool ok=true;
        for(int i=0; i<26; ++i)
            if(din[i]!=dout[i]){
                if(din[i]==dout[i]+1) ++e;
                else if(din[i]+1==dout[i]) ++s;
                else {ok=false; break;}
            }
        // 有向图Euler path判定
        // 或者起点和终点数量都是0(形成环)
        // 或者起点和终点数量都是1
        if(!(!s&&!e||s==1 && e==1)) ok=false;

        // 判断连通性
        int start=0;
        while(!dout[start]) ++start;
        for(int i=start; i<26; ++i){
            if(dout[i]==din[i]+1) {start=i; break;}
        }
        dfs(start);
        if(cnt!=n) ok=false;
        if(ok) cout<<"Ordering is possible."<<endl;
        else cout<<"The door cannot be opened."<<endl;
    }

    return 0;
}