LOJ-10106（有向图欧拉回路的判断）

LOJ-10106（有向图欧拉回路的判断）

题目链接：传送门

思路：

（1）将每个单词视为有向路径，单词的起始字母是起始节点，末尾字母是终止节点，然后找由字母建立的有向图

是否是欧拉图或者半欧拉图。

（2）先用并查集判断是否连通，再判断入度与出度的·关系是否符合要求。

有向图的欧拉图的判断

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int maxn = ;

int fa[],in[],out[];

string ss[maxn];

struct Edge{

    int to,next,id;

}edge[maxn*];

int vis[maxn],head[maxn],tot;

int f(int x)

{

    if(fa[x]==) return x;

    else return fa[x]=f(fa[x]);

}

void Init()

{

    memset(fa,,sizeof(fa));

    memset(in,,sizeof(in));

    memset(out,,sizeof(out));

    memset(vis,,sizeof(vis));

    memset(head,,sizeof(head));

    tot=;

}

void add(int x,int y,int w)

{

    edge[tot].to=y;

    edge[tot].next=head[x];

    edge[tot].id=w;

    head[x]=tot++;

}

int main(void)

{

    //printf("%d\n",'z'-'a'+1);

    int N,i,n,j,x,y,t1,t2;

    scanf("%d",&N);

    while(N--){

        scanf("%d",&n);

        Init();

        for(i=;i<=n;i++){

            cin>>ss[i];

            x=ss[i][]-'a'+;

            y=ss[i][ss[i].length()-]-'a'+;

            t1=f(x);t2=f(y);

            if(t1!=t2) fa[t2]=t1;

            in[y]++;

            out[x]++;

            add(x,y,i);

        }

        int fg=;

        x=f(x);

        for(i=;i<=n;i++){

            y=ss[i][]-'a'+;

            if(f(y)!=x){

                fg=;break;

            }

            y==ss[i][ss[i].length()-]-'a'+;

            if(f(y)!=x){

                fg=;break;

            }

        }

        if(fg==){

            int tt=,cc=;

            for(i=;i<=;i++){

                if(abs(in[i]-out[i])>){

                    tt=;break;

                }

                else if(abs(in[i]-out[i])==){

                    cc+=(in[i]-out[i]);

                }

            }

            if(tt==&&cc==) printf("Ordering is possible.\n");

            else printf("The door cannot be opened.\n");

        }

        else printf("The door cannot be opened.\n");

    }

    return ;

}