UVA10129 POJ1386 HDU1116 ZOJ2016 Play on Words【欧拉回路+并查集】

问题链接：UVA10129 POJ1386 HDU1116 ZOJ2016 Play on Words。

问题简述：先输入测试用例数T，每个测试用例包括整数N和N个单词数，问这些单词首尾字母能否接成一条龙？

问题分析：这是一个单词接龙问题，一个单词的尾字母和另外一个单词的首字母相同则可以接成龙。其中，每个单词只包含小写字母。单词的首字母和尾字母可以作为图的一个结点，从单词的首字母到尾字母画一条有向边，单词接龙问题就变成一笔画问题，或称为欧拉路径问题。

欧拉路径问题有两个条件，一是图是联通的；二是所有结点出入度相同，或者只有两个结点出入度差为1。

程序说明：用并查集来判定图是否是联通的。

程序提交后，除了POJ1386出现TLE，其他３个在线评判都AC了。在高人指点之下，程序中增加了69行的代码“ios::sync_with_stdio(false);”，就都可以通过了。这是由于C++的输入输出比较慢的原因，通过这行代码，改善了I/O的速度。

这个语句也可以写为“std::ios::sync_with_stdio(false);”。担心C++输入输出慢，可以使用该语句改善速度。

AC的C++语言程序如下：

/* UVA10129 Play on Words */

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

const int N = 26;

// 并查集类
int v[N];
class UF {
private:
    int length;
public:
    UF(int n) {
        length = n;
        for(int i=0; i<=n; i++)
            v[i] = i;
    }

    // 压缩
    int Find(int x) {
        if(x == v[x])
            return x;
        else
            return v[x] = Find(v[x]);
    }

    bool Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        if(x == y) {
            return false;
        } else {
            v[x] = y;
            return true;
        }
    }
};

int degreeout[N];
int degreein[N];

// 出入度检查：return nopathflag
bool degreeincheck()
{
    int startcount = 0, endcount = 0;

    for(int i=0; i<N; i++)
        if(degreeout[i] != degreein[i]) {
            if((degreeout[i] - degreein[i]) == 1) {
                if(++startcount > 1)
                    return true;
            } else if((degreeout[i] - degreein[i]) == -1) {
                if(++endcount > 1)
                    return true;
            } else
                return true;
        }
    return false;
}

int main()
{
    int t, n, src, dest;

    ios::sync_with_stdio(false);

    cin >> t;
    while(t--) {
        UF uf(N+1);

        memset(degreeout, 0, sizeof(degreeout));
        memset(degreein, 0, sizeof(degreein));

        // 输入测试用例的数据，构建并查集，统计各个结点的度
        cin >> n;
        string s;
        while(n--) {
            cin >> s;

            src = s[0] - 'a';
            dest = s[s.size() - 1] - 'a';

            degreeout[src]++;
            degreein[dest]++;

            uf.Union(src, dest);
        }

        // 判断图的联通性
        bool nopathflag = false;
        int root = -1;
        for(int i=0; i<N; i++) {
            if(degreeout[i] || degreein[i]) {
                if(root == -1)
                    root = uf.Find(i);
                else if(uf.Find(i) != root) {
                    nopathflag = true;
                    break;
                }
            }
        }

        // 判定是否存在欧拉路径：出入度检查
        if(!nopathflag)
            nopathflag = degreeincheck();

        // 输出结果
        if(nopathflag)
            cout << "The door cannot be opened." << endl;
        else
            cout << "Ordering is possible." << endl;

    }

    return 0;
}

UVA10129 POJ1386 HDU1116 ZOJ2016 Play on Words【欧拉回路+并查集】

相关推荐