E. Split Into Two Sets - 题解

比赛与标签

比赛: Codeforces Round 805 (Div. 3) 标签: dfs and similar, dsu, graphs 难度: *1600

题目大意喵~

喵~ 主人 sama，下午好呀！今天我们来解决一个超级有趣的的多米诺骨牌分组问题，呐！(ฅ'ω'ฅ)

题目是这样子的：我们有 n 个多米诺骨牌，n 是一个偶数。每个骨牌上都有两个数字，范围都在 1 到 n 之间。

我们的任务是，判断一下能不能把这 n 个骨牌分成两个数量相等的集合（每个集合 n/2 个骨牌），并且满足一个神奇的条件：在每一个集合内部，所有骨牌上的数字都必须是独一无二的。

举个栗子，如果一个集合里有 {1,2} 和 {3,4}，那么这个集合包含的数字是 {1, 2, 3, 4}，它们都不一样，所以是合法的，喵~。但如果集合里有 {1,2} 和 {1,3}，数字 1 就重复出现了，这样就不行啦！

如果可以成功分组，我们就开心地输出 "YES"，如果不行的话，就只能遗憾地输出 "NO" 咯。

解题思路：猫猫的图论魔法！

看到这种“配对”、“关系”的问题，我们的猫猫直觉就告诉我们，这一定和图论有关的说！(๑•̀ㅂ•́)و✧

第一步：把问题变成一张图

让我们施展一点小魔法，把问题转化一下：

• 把数字 1 到 n 看作是图上的 n 个点（顶点）。
• 把每一个多米诺骨牌 {a, b} 看作是连接点 a 和点 b 的一条无向边。

这样一来，n 个多米诺骨牌就变成了一张有 n 个点和 n 条边的图啦！

第二步：发现第一个重要线索

题目要求，分成的两个集合（我们叫它集合A和集合B吧）内部数字不能重复。

• 集合A有 n/2 个骨牌，总共有 n 个数字。为了不重复，这 n 个数字必须恰好是 1, 2, ..., n。
• 同理，集合B的 n/2 个骨牌上的 n 个数字，也必须恰好是 1, 2, ..., n。

这意味着什么呢？这意味着，对于任何一个数字 k（从1到n），它必须在集合A的骨牌里出现一次，也在集合B的骨牌里出现一次。所以，把所有 n 个骨牌合起来看，每个数字都必须恰好出现两次！

在我们的图论模型里，一个点 k 的度数（degree）就是连接它的边的数量，也就是数字 k 在所有骨牌上出现的总次数。所以，我们得出了第一个至关重要的结论：

如果存在任何一个数字的出现次数不等于2（即图中任何一个点的度数不为2），那么绝对不可能完成分组，直接输出 "NO"。

第三步：揭开环的秘密

好耶！如果所有点的度数都恰好为 2，我们的图会是什么样子的呢？它会是一堆互不相连的环（Cycle）！就像一串串漂亮的珍珠项链一样，呐~

现在，问题就变成了：我们能把这些环上的边（多米诺骨牌）分成两组（集合A和集合B），使得在每组中，每个点都只被一条边连接吗？

这其实是一个经典的图论问题——边的二着色（2-edge-coloring）。我们尝试给每条边涂上颜色A或颜色B。

• 想象一下，在一个环上，我们给第一条边 {v1, v2} 涂上颜色A（表示放进集合A）。
• 那么，与 v2 相连的另一条边 {v2, v3} 就必须涂上颜色B（放进集合B），不然 v2 在集合A里就出现两次了。
• 接着，与 v3 相连的边 {v3, v4} 就必须涂上颜色A...

我们发现，边的颜色必须是 A, B, A, B, ... 这样交替出现的。

• 如果环的长度是偶数：比如长度为4的环 v1-v2-v3-v4-v1。边 {v1,v2}(A), {v2,v3}(B), {v3,v4}(A), {v4,v1}(B)。看，回到起点时，连接 v1 的两条边 {v1,v2} 和 {v4,v1} 颜色不同，完美！
• 如果环的长度是奇数：比如长度为3的环 v1-v2-v3-v1。边 {v1,v2}(A), {v2,v3}(B), {v3,v1}(A)。呀！回到起点时，连接 v1 的两条边 {v1,v2} 和 {v3,v1} 都是颜色A，冲突了！

所以，我们得到了最终的制胜法宝：

只有当图中的所有环的长度都是偶数时，才能成功分组！

总结一下策略：

1. 建图：将数字看作点，多米诺骨牌看作边。
2. 度数检查：检查所有点的度数是否都为 2。如果不是，输出 "NO"。
3. 环长度检查：如果度数都为 2，就遍历图中的每一个环。可以用 BFS 或 DFS 来找到一个连通分量（也就是一个环），并计算它的长度（顶点数）。
4. 判断：如果所有环的长度都是偶数，输出 "YES"。只要有一个环的长度是奇数，就输出 "NO"。

代码实现，冲呀！

#include <iostream>
#include <vector>
#include <numeric>
#include <queue>

// 这个函数用来解决单个测试用例，喵~
void solve() {
    int n;
    std::cin >> n;
    
    // 邻接表，用来存我们的图，喵~
    // 顶点编号从 1 到 n
    std::vector<std::vector<int>> adj(n + 1);
    // 记录每个数字（顶点）出现了几次（度数）
    std::vector<int> degree(n + 1, 0);
    
    // 读入n个多米诺骨牌，然后建图，同时计算每个点的度数
    for (int i = 0; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    // 第一个关键检查！每个数字必须恰好出现两次，也就是每个点的度数都得是2才行
    bool possible = true;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] != 2) {
            possible = false;
            break;
        }
    }

    if (!possible) {
        std::cout << "NO\n";
        return;
    }

    // 如果度数检查通过了，图就是一堆环。我们来一个个检查这些环
    // 用一个 visited 数组来标记访问过的点，防止重复计算
    std::vector<bool> visited(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            // 找到一个还没访问过的环的起点！
            // 我们来计算这个环的长度
            int cycle_len = 0;
            std::queue<int> q;
            
            q.push(i);
            visited[i] = true;
            
            // 用BFS来遍历整个环，并计算环里有多少个点（也就是环的长度）
            while(!q.empty()){
                int u = q.front();
                q.pop();
                cycle_len++;
                
                for(int v : adj[u]){
                    if(!visited[v]){
                        visited[v] = true;
                        q.push(v);
                    }
                }
            }
            
            // 第二个关键检查！如果环的长度是奇数，那就没办法完美分组了，呜呜~
            if (cycle_len % 2 != 0) {
                possible = false;
                break;
            }
        }
    }

    if (possible) {
        // 如果所有检查都通过了，就说明可以分组，YES！
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // 让输入输出快一点的魔法~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

复杂度分析

• 时间复杂度: O(n) 的说。对于每个测试用例，我们建图需要 O(n) 的时间，遍历每个顶点和每条边也都是常数次（度数检查一次，BFS 遍历一次）。所以整体是线性的，非常快！
• 空间复杂度: O(n) 的说。我们主要用了邻接表 adj 来存图，还有 degree 和 visited 数组，它们的空间都和顶点数 n 成正比。

知识点与总结

这真是一道把问题抽象化的好题呢！主人 sama 一定也学到了很多吧！

1. 图论建模: 这道题最重要的一步就是把问题转化成图论模型！把“数字”看作“点”，把“多米诺骨牌”看作“边”，是解决这类问题的经典思路呐。
2. 图的性质: “所有点度数均为2的图，必然由若干个不相交的环组成”，理解这个性质是解题的关键。它能让复杂的问题瞬间清晰起来。
3. 二着色思想: 虽然我们没有直接写二分图判定的代码，但“偶数环”的结论本质上来源于图的二着色思想。将边分成两组，其实就是对边进行二着色。这是一个非常有用的思想，喵~
4. 实现技巧: 处理多组测试用例时，一定要注意初始化！这题的代码把 solve 函数独立出来，每次调用都会创建新的 vector，这样就很安全，不会被上个测试用例的数据干扰。

希望这篇题解能帮到你，喵~！一起继续努力，攻克更多有趣的题目吧！(ง •̀_•́)ง