🪴 Edwin Aze's Blog

最近文章

最近笔记

Play on Words

4分钟阅读

欧拉路径 并查集 T3 有 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。

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

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

输入格式

第一行包含整数 ，表示共有 组测试数据。

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

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

一个单词可能出现多次。

输出格式

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

数据范围

, 单 词 长 度 均 不 超 过

样例

输入

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. 对于有向图，所有边都是连通。 (1)存在欧拉路径的充分必要条件:要么所有点的出度均等于入度;要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点:一个满足出度比入度多1(起点)，另一个满足入度比出度多1(终点).

故只需要判断是否满足条件, 且是连通图。

边读入边记录出入度, 用 start 和 end 记录当前符合起点或终点的点数量。只有其他点都入度都等于出度或者start和end点数量是0个或者1个。

判断连通可以用并查集, 刚开始建边时就合并, 最后枚举所有出现的字符, 判断是否跟之前的在一个集合里, 若不在说明不连通。

记得用st数组标记目前出现过的字符。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int din[29], dout[29], f[N];
int n;
bool st[N];
 
int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        memset(din, 0, sizeof din);
        memset(dout, 0, sizeof dout);
        memset(st, 0, sizeof st);
        for (int i = 0; i < 26; i++)
            f[i] = i;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            string s;
            cin >> s;
            int b = s[s.size() - 1] - 'a', a = s[0] - 'a';
            st[a] = st[b] = true;
            f[find(a)] = find(b);
            din[b]++;
            dout[a]++;
        }
        bool flag = true;
        int start = 0, end = 0;
        for (int i = 0; i < 26; i++)
            if (din[i] != dout[i] && st[i])
            {
                if (din[i] == dout[i] + 1)
                    end++;
                else if (din[i] + 1 == dout[i])
                    start++;
                else
                {
                    flag = false;
                    break;
                }
            }
        if (flag && !((!start && !end) || (start == 1 && end == 1)))
            flag = false;
 
        int p = -1;
        for (int i = 0; i < 26; i++)
        {
            if (!st[i])
                continue;
            if (p == -1)
                p = find(i);
            else if (p != find(i))
            {
                flag = false;
                break;
            }
        }
        if (flag)
            puts("Ordering is possible.");
        else
            puts("The door cannot be opened.");
    }
 
    return 0;
}

反向链接