「题解」 UVa10129 Play on Words

· · 题解

题意：给出n个单词，判断能否组成环。

把每个单词想象成它的首字母向尾字母连边（有向边）。 例如：acm这个单词，可以看作a向b连接，所以b的入度+1，a的出度+1。

有向图中欧拉回路的定义：

简单来说就是

  • 每个节点的入度出度都相等。
  • 除两个节点外，其它节点全部满足上一条件。而这两个节点满足，其中一个的入度比出度大1，另一个的出度比入度大1

这时会有一个特殊情况： 例如：eye这个单词，处理后变成e向e连了一条有向边。

可以看下面的一组样例，

发现eye这个单词与其它的单词没有连边，所以应该先判断图的联通性，再 判断是否构成欧拉回路。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>

const int MAX_N = 100000 + 10;
std::string G[MAX_N];

bool vis[27];
int in[27], out[27], fa[27];

inline void Init() {
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= 26; i++) fa[i] = i;
}

int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

int main() {
    std::ios::sync_with_stdio(false);

    int T; std::cin >> T;
    while (T--) {
        int n; std::cin >> n;

        Init();

        for (int i = 1; i <= n; i++) {
            std::cin >> G[i];
            in[G[i].back() - 'a' + 1]++;
            out[G[i].front() - 'a' + 1]++;

            vis[G[i].back() - 'a' + 1] = vis[G[i].front() - 'a' + 1] = true;

            int fx = find(G[i].back() - 'a' + 1), fy = find(G[i].front() - 'a' + 1);
            if (fx != fy) {
                fa[fx] = fy;
            }
        }

        int cnt = 0;
        for (int i = 1; i <= 26; i++) {
            if (vis[i] && find(i) == i) ++cnt;
        }

        if (cnt > 1) { // 不连通
            puts("The door cannot be opened.");
            continue;
        }

        std::vector<int> odd;
        for (int i = 1; i <= 26; i++) {
            if (vis[i] && in[i] != out[i]) odd.push_back(i);
        }

        if (odd.size() != 0 && odd.size() != 2) { // 奇点个数不为0个或2个
            puts("The door cannot be opened.");
            continue;
        }

        if (odd.empty()) { //全为偶点
            puts("Ordering is possible.");
            continue;
        }

        if (in[odd.front()] - out[odd.front()] == 1 && out[odd.back()] - in[odd.back()] == 1) {
            puts("Ordering is possible.");
            continue;
        }

        if (out[odd.front()] - in[odd.front()] == 1 && in[odd.back()] - out[odd.back()] == 1) {
            puts("Ordering is possible.");
            continue;
        }

        puts("The door cannot be opened.");
    }

    return 0;
}