python/TangDou/AcWing/EulerPath/1185.md

AcWing 1185 单词游戏

一、题目描述

有 N 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。

你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。

请你编写一个程序，判断是否能达到这一要求。

输入格式 第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N，表示盘子数量。

接下来 N 行，每行包含一个小写字母字符串，表示一个盘子上的单词。

一个单词可能出现多次。

输出格式 如果存在合法解，则输出Ordering is possible.，否则输出The door cannot be opened.。

数据范围 1≤N≤10^5, 单词长度均不超过1000

输入样例：

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

输出样例：

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

二、前导知识

1、欧拉通路 与 欧拉回路

能一笔画的存在欧拉通路,如果起点和终点重合的话就是存在欧拉回路。

2、欧拉通路的判定

要想知道一个 有向图 是不是能一笔画，方法如下：

• ① 把它对应的无向图整出来 (基图)
• ② 判断基图是不是连通,方法：dfs 或者 并查集
• ③ 存在一个且仅一个顶点的入度比出度大1、一个且仅一个顶点的入度比出度小1，其它所有顶点的入度等于出度

三、题目解析

把单词看成一条边，每输入一个单词看成从首字母到尾字母的一条边。这样我们就能通过欧拉路径的分析方法判断是否存在从一个点出发连接所有边的路径（即欧拉路径）

注意：这里不一定是回路，能连接所有单词即可

因为是有向边开两个度数数组，din和dout，欧拉路径除了终点和起点外要求其他每个点入度=出度，判断每个点的入度不等于出度有三种可能：起点、终点、不存在欧拉路径。

值得注意的是如果这些边中度数已经不满足要求，即起点或终点个数不止一个，或起点数!=终点数的时候都是属于不存在欧拉路径的情况。因此要先判断，再dfs。因为dfs在要保证正确性的前提下只能判断是否连通，即最后cnt == m ? 连通 : 不连通。因为不存在欧拉路径时亦可能 cnt = m(比如两个环)

总结：欧拉路径除了连通性都用din和dout数组来判断，连通性用dfs来判断。

dfs

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 100010;

int m;
int din[N], dout[N];
int cnt;

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 欧拉通路+删边优化+边记数
void dfs(int u) {
    for (int i = h[u]; ~i; i = h[u]) {
        h[u] = ne[i];
        dfs(e[i]);
        cnt++;
    }
}

int main() {
    char str[N]; // char数组的性能比string要强！建议使用此方法

    int T;
    scanf("%d", &T);
    while (T--) {
        memset(h, -1, sizeof h);
        idx = cnt = 0;
        memset(din, 0, sizeof din);
        memset(dout, 0, sizeof dout);
        scanf("%d", &m);

        for (int i = 0; i < m; i++) {
            scanf("%s", str); // 配合字符数组完成字符串读入
            int a = str[0] - 'a', b = str[strlen(str) - 1] - 'a';
            add(a, b); // 有向图建边
            din[b]++, dout[a]++;
        }

        // 枚举每个字母映射的节点0~25
        int start = 0, s = 0, e = 0; // start:起点，s:起点个数,e:终点个数
        for (int i = 0; i < 26; i++)
            if (din[i] != dout[i]) {            // 如果入度与出度不相等,那么必须是一个起点，一个终点
                if (din[i] == dout[i] - 1)      // 入度=出度-1 ->起点
                    start = i, s++;             // 记录起点
                else if (din[i] == dout[i] + 1) // 入度=出度+1 ->终点
                    e++;
                else { // 没有欧拉通路,标识start=-1,表示检查失败
                    start = -1;
                    break;
                }
            }
        // start==-1   : 不存在欧拉路径
        // s> 1 || e>1 : 起点数量大于1，或者终点数量大于1
        if (start == -1 || s > 1 || e > 1) {
            puts("The door cannot be opened.");
            continue;
        }

        // 用dfs判断是否连通,用上面的欧拉定理先把度的事处理完，再dfs，可以提速
        dfs(start);

        // 如果枚举到的边数小于图中的边，表示没走全，说明图不连通
        if (cnt < m)
            puts("The door cannot be opened.");
        else
            puts("Ordering is possible.");
    }
    return 0;
}

并查集

#include <bits/stdc++.h>
using namespace std;

const int N = 30;

int m;
int din[N], dout[N], p[N];
bool st[N];

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

int main() {
    char str[1010];

    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &m);
        memset(din, 0, sizeof din);
        memset(dout, 0, sizeof dout);
        memset(st, 0, sizeof st);
        for (int i = 0; i < 26; i++) p[i] = i;

        for (int i = 0; i < m; i++) {
            scanf("%s", str);
            int len = strlen(str);
            int a = str[0] - 'a', b = str[len - 1] - 'a';
            st[a] = st[b] = 1;
            dout[a]++, din[b]++;
            p[find(a)] = find(b);
        }

        // 利用欧拉图判断的定理检查
        int start = 0, s = 0, e = 0, flag = 1; // start:起点，s:起点个数,e:终点个数
        for (int i = 0; i < 26; i++)
            if (din[i] != dout[i]) {            // 如果入度与出度不相等,那么必须是一个起点，一个终点
                if (din[i] == dout[i] - 1)      // 入度=出度-1 ->起点
                    start = i, s++;             // 记录起点
                else if (din[i] == dout[i] + 1) // 入度=出度+1 ->终点
                    e++;
                else { // 没有欧拉通路,标识start=-1,表示检查失败
                    start = -1;
                    break;
                }
            }
        if (start == -1 || s > 1 || e > 1) flag = 0;

        // 判连通
        for (int i = 0; i < 26; i++) {
            if (!st[i]) continue;         // 只处理出现的点
            if (find(start) != find(i)) { // 找到不是一个家庭的成员
                flag = 0;
                break;
            }
        }

        if (flag)
            puts("Ordering is possible.");
        else
            puts("The door cannot be opened.");
    }

    return 0;
}