UVA10129 单词 Play on Words

本文主要是介绍UVA10129 单词 Play on Words，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

难度：4
知识点：欧拉回路

没怎么学过图论，算法竞赛入门经典的欧拉回路看的一愣一愣的，欧拉道路和欧拉回路也分不清，就记住了怎么做题，对于无向图，充分条件是，奇点个数小于等于2，奇点也就是度数为奇数的点，并且奇点个数是2的时候一定是一个点为起点，另一个点为终点，当然，图一定要是联通的，对于有向图，充分条件是最多有两个点的出度和入度不同，并且如果这样的点有两个的话，那么一定要其中一个点的出度比入度大一，作为起点，另一个点的出度比入度小一，作为终点，当然这时候也要求图在无向图的意义上是联通的，这就是欧拉回路做题时候判定的思路

然后回到本题，本题需要用到图论的模型，那就是把单词最前面的字母，最后面的字母当成两个点，整个单词当成最前面那个点到后面那个点的有向边，这样就可以建图了，然后怎么判定联通，一开始想用dfs，但是一看这个单词，可能首尾两个字母相同，这不就是自环，感觉有点悬，而且这个模型的话，最多只有26个点，两个点之间可能有很多边，不止一条，感觉怕出差错，所以就用了并查集，不过做完之后想一想，用dfs也没什么影响，该能判断还是能判断，就是自己的图论的建图什么基本功太弱了，就没写，

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;

int fa[30];

int findfather(int v) {
    if (v == fa[v]) return v;
    return fa[v] = findfather(fa[v]);
}

void Union(int a, int b) {
    fa[findfather(a)] = findfather(b);
}

int main() {
    int t; cin >> t;
    while (t--) {
        for (int i = 0; i < 30; i++) fa[i] = i;
        int n; cin >> n;
        int out[26] = {}, in[26] = {};
        int Hash[26] = {};
        for (int i = 0; i < n; i++) {
            string s; cin >> s;
            int len = sz(s);
            if (len == 1) { Hash[s[0] - 'a'] = 1; continue; }
            int x1 = s[0] - 'a', x2 = s[len - 1] - 'a';
            Hash[x1] = 1; Hash[x2] = 1;
            out[x1]++; in[x2]++;
            Union(x1, x2);
        }
        set<int> st;
        for (int i = 0; i < 26; i++) {
            if (Hash[i]) st.insert(findfather(i));
        }
        if (sz(st) > 1) { cout << "The door cannot be opened.\n"; continue; }
        pa p[30]; int cnt = 0;
        for (int i = 0; i < 26; i++) {
            if (Hash[i] && in[i] != out[i]) p[cnt++] = make_pair(in[i], out[i]);
        }
        if (cnt > 2) { cout << "The door cannot be opened.\n"; continue; }
        if (cnt == 2 && !(p[0].fi == p[0].se + 1 && p[1].fi == p[1].se - 1 || p[0].fi == p[0].se - 1 && p[1].fi == p[1].se + 1)) {
            cout << "The door cannot be opened.\n"; continue;
        }
        cout << "Ordering is possible.\n";
    }
    return 0;
}

这篇关于UVA10129 单词 Play on Words的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！