单词游戏

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1843 字
T组数据，每组N个单词，要求排成一列使前一个
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1528
// 题意：T 组数据，每组 N 个单词，要求排成一列使前一个单词的末字母等于后一个的首字母，能排则输出 Ordering is possible.，否则输出 The door cannot be opened.。
// 思路：每个单词连一条首字母到末字母的有向边，问题变成 26 个点的有向图是否存在欧拉路径：所有有度数的点在同一个并查集里，且度数差绝对值之和只能为 0（欧拉回路）或 2（欧拉通路，恰一个点出比入多 1、一个点入比出多 1）。
// 1. 并查集按无向合并，用来判断「有度数的点」是否连通，孤立字母没有边不参与判断。
// 2. 度数条件用 Σ|出度-入度| 直接判定：必须恰为 0 或 2，这样能同时排除「ok+ok」这种某点差达 ±2 的非法情况。
// 复杂度：O(T * (N + 26)) 时间 / O(26) 空间
// 易错点：只判断度数不够，必须由有度数的点构成单个连通块，否则「acm、ibm」这种两条边不连通的情况会被误判成有解。
// 易错点：输出句子里的标点与大小写要照抄，句末的点不能丢，单词的首末字母取 s[0] 与 s.back()。
#include <bits/stdc++.h>
using namespace std;
int fa[26];
int find(int x){
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
void merge(int a, int b){
    int x = find(a);
    int y = find(b);
    if(x != y) fa[x] = y;
}
int main(){
    int T;
    if(!(cin >> T)) return 0;
    while(T--){
        int N;
        cin >> N;
        int ind[26], outd[26];
        for(int i = 0; i < 26; i++){
            ind[i] = 0;
            outd[i] = 0;
            fa[i] = i;
        }
        for(int i = 0; i < N; i++){
            string s;
            cin >> s;
            int a = s[0] - 'a';
            int b = s[(int)s.size() - 1] - 'a';
            outd[a]++;
            ind[b]++;
            merge(a, b);
        }
        int root = -1;
        bool connected = true;
        int sumabs = 0;
        for(int i = 0; i < 26; i++){
            if(ind[i] == 0 && outd[i] == 0) continue;
            int r = find(i);
            if(root == -1) root = r;
            else if(root != r) connected = false;
            sumabs += abs(outd[i] - ind[i]);
        }
        // 欧拉路径条件：有度数的点连通，且度数差之和只能为 0（欧拉回路）或 2（欧拉通路）
        bool ok = connected && (sumabs == 0 || sumabs == 2);
        if(ok) cout << "Ordering is possible." << "\n";
        else cout << "The door cannot be opened." << "\n";
    }
    return 0;
}
单词游戏

正文

一本通·提高篇的其它内容
