Play on Words UVA - 10129 （欧拉回路）

题目链接：https://vjudge.net/problem/UVA-10129

题目大意：输入N 代表有n个字符串每个字符串最长1000 要求你把所有的字符串连成一个序列每个字符串的第一个字母是前一个字符串的最后一个字母

思路：这是学的欧拉回路的第一道题，把单词的首字母和尾字母看做结点，单词看作边，判断能否找出一条欧拉回路就行了

首先要知道什么是欧拉回路：

第一个条件：图必须是连通的

第二个条件：最多只有两个奇点（出度和入度不相等的点）

满足上面两个条件的就是欧拉回路

如果有两个奇点，必须从一个奇点出发另一个奇点终止。不存在奇点的话任一点出发回到该点

注意：图是连通的是前提。

求欧拉回路有两种做法一种是dfs 一种是并查集

我两种都写了，但是用dfs的做法一直wa 到现在也不明白错在哪了。所以这里就列出并查集的做法吧

#include<iostream>

#include<string.h>

#include<vector>

using namespace std;

const int maxn=+;

int pa[];

int findset(int x)//找到它的祖先

{

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

    return pa[x]=findset(pa[x]);

}

int used[],deg[];//是否出现过  度数

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        int n;

        char word[maxn];

        cin>>n;

        memset(used,,sizeof(used));

        memset(deg,,sizeof(deg));

        for(int ch='a';ch<='z';ch++) pa[ch]=ch;//初始化并查集

        int cc=;//连通块个数

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

        {

            cin>>word;

            char c1=word[],c2=word[strlen(word)-];

            deg[c1]++;//出度的话 ++

            deg[c2]--;//入度  --

            used[c1]=used[c2]=;//标记为出现过

            int s1=findset(c1),s2=findset(c2);//找到他们的祖先

            if(s1!=s2)//不是同一个祖先

            {

                pa[s1]=s2;

                cc--;//连通块减一

            }

        }

        vector<int> d;

        for(int ch='a';ch<='z';ch++)

        {

            if(!used[ch]) cc--;//没出现过的字母

            else if(deg[ch]!=) d.push_back(deg[ch]);//出度和入度不相等的结点

            //=0代表出度和入度相等的结点 不需要考虑

        }

        bool ok=false;

        if(cc==&&(d.empty()||(d.size()==&&(d[]==||d[]==-)))) ok=true;//cc=1代表只剩下一个块   为空代表成环  不为空 为2的话 一个是出度一个是入度

        if(ok) cout<<"Ordering is possible."<<endl;

        else cout<<"The door cannot be opened."<<endl;

    }

    return ;

}

巴特西

Play on Words UVA - 10129 （欧拉回路）

最新文章

热门文章