Play on Words（并查集+欧拉路）

小咪咪 2022-08-02 04:38 105阅读 0赞

![20150707165428216][]

这个题目要运用到欧拉路得相关知识，并且也要并查集，题目说的是：给你n个单词，要你判断这些单词能不能首尾相连。理解题目意思后，进行转化，输入字符串，提取首位字母作为下标来表示两节点的出现，以及相对应节点入度和出度的增加，转化为并查集的应用即可。那么从可以想象一幅由首位字母节点构成的图，当且仅当图是一条欧拉回路或者欧拉通路的时候，才能满足题目的要求，至于欧拉回路和欧拉通路的判定可以总结为如下：  
1）所有的点联通  
2）欧拉回路中所有点的入度和出度一样。

3）欧拉通路中起点的入度 - 出度 = 1，终点的 初度 - 入度 = 1， 其他的所有点入度 = 出度；

### 无向图存在欧拉回路条件 ###

一个无向图存在欧拉回路，当且仅当该图所有顶点度数都是偶数。

### 有向图存在欧拉回路条件 ###

一个有向图存在欧拉回路，且所有顶点的入度等于出度

**这里我把单词的头作为出度单词的尾作为入度，其实都一样！**

#include<cstdio>
    #include<iostream>
    #include<string>
    #include<cstring>
    const int N=30;
    using namespace std;
    int a[N];//记录老大是谁？
    int in[N];//记录入读！
    int out[N];//记录出度！
    int vis[N];//记录是否访问！
    int p[30];//记录头和尾
    int Find(int x)
    {
        int r=x;
        while(r!=a[r])
            r=a[r];
        return r;
    }//这个就是找老大的函数，什么时候停止？就是当一个人的老大是他自己的时候！
    void mix(int x,int y)
    {
        int fx=Find(x),fy=Find(y);//首先要找到他们各自的老大
        if(fx!=fy)//如果他们的老大不相等，要合并就必须其中的一个老大向另外一个老大称老大
        {
            a[fy]=fx;
        }
    }
    int main()
    {
        int t,n,i,f,j,l,c,b;
        string s;
        cin>>t;
        while(t--)
        {
            memset(vis,0,sizeof(vis));
            memset(out,0,sizeof(out));
            memset(in,0,sizeof(in));
            for(i=0;i<N;i++)
            {
                a[i]=i;
            }
            cin>>n;
            for(i=0;i<n;i++)
            {
                cin>>s;
                l = s.length();
                b = s[0]-'a';
                c = s[l-1]-'a';
                out[b]++;
                in[c]++;
                vis[b]=vis[c]=1;
                mix(b,c);
            }
            for(i=0,j=0,f=0;i<N;i++)
            {
                if(vis[i]&&Find(i)==i)
                {
                    f++;
                }
                if(in[i]!=out[i])//出度不等于入读！
                {
                    p[j++]=i;
                }
            }
            if(f>1)
            {
                cout<<"The door cannot be opened."<<endl;
                continue;
            }
            if(j==0)
            {
                cout<<"Ordering is possible."<<endl;//欧拉通路！
                continue;
            }
            if(j==2)
            {
                if((in[p[0]]-out[p[0]]==1&&out[p[1]]-in[p[1]]==1)||(in[p[1]]-out[p[1]]==1&&out[p[0]]-in[p[0]]==1))
                {
                    cout<<"Ordering is possible."<<endl;//欧拉回路！
                }
                else
                {
                    cout<<"The door cannot be opened."<<endl;
                }
            }
            else
            {
                cout<<"The door cannot be opened."<<endl;
            }
        }
    }

[20150707165428216]: /images/20220731/bca5ec10de1a4eec993627518a70cc32.png