E. Cover it! - 题解

比赛与标签

比赛: Codeforces Round 565 (Div. 3) 标签: dfs and similar, dsu, graphs, shortest paths, trees 难度: *1700

题目大意喵~

主人你好呀~！这次的任务是这样的呐：我们拿到一个无向、无权、连通的图，它有 n 个顶点和 m 条边。我们的目标是，从里面选出最多 ⌊n/2⌋ 个顶点，组成一个“守护者”小队，喵~

这个小队要非常厉害，厉害到图里每一个没有被选中的顶点，都至少和一个“守护者”顶点是邻居（也就是有边直接连着）。

题目保证一定有解，而且我们只要随便找出一组符合条件的解就可以啦！是不是听起来很有趣的说？

解题思路 - 染色魔法时间！

呀哈~！看到这个题目，是不是有点小懵圈，不知道该选哪些点呢？别担心，让本猫娘来教你一个超级好用的“染色魔法”！

这个问题的核心是要用一小部分点（“守护者”）去“覆盖”所有其他的点。我们可以换个角度想，如果我们把所有顶点分成两组，A 组和 B 组，然后我们选择其中一组作为“守护者”，那么这一组就必须能覆盖另一组。这意味着，另一组里的任何一个点，都必须和我们选的这组里的某个点有边相连，对吧？

这听起来是不是很像……二分图染色呀！喵呜~

一个图是二分图，当且仅当我们可以把它的所有顶点染成两种颜色（比如粉色和蓝色），使得任意一条边的两个端点颜色都不同。也就是说，不存在粉色-粉色或者蓝色-蓝色的边。

我们的解法就是基于这个思路：

进行二分图染色：我们可以从任意一个点（比如1号点）开始，用 广度优先搜索（BFS） 来进行染色。BFS就像探索迷宫一样，一层一层地往外走，这正好适合我们交替染色的需求！
- 我们把起点（1号点）的深度设为0，可以想象成染成“偶数色”。
- 所有与起点直接相连的邻居，它们的深度就是1，我们染成“奇数色”。
- 与深度1的顶点相连的、还没访问过的顶点，深度就是2，我们再染成“偶数色”。
- ……以此类推，深度(v) = 深度(u) + 1。
划分集合：BFS结束后，所有的点都有了一个深度值。我们就根据深度的奇偶性，把所有顶点分成两个集合：
- set0：所有深度为偶数的顶点。
- set1：所有深度为奇数的顶点。
为什么这样可行呢？因为在图中，任意一条边 (u, v) 连接的两个顶点，它们的深度值一定只相差1。所以，一个顶点的深度是偶数，另一个就必然是奇数。这意味着，我们绝对找不到一条边，它的两个端点都在 set0 里，或者都在 set1 里！所有的边都是连接 set0 和 set1 的。
选择哪个集合呢？
- 如果我们选择 set0 作为我们的“守护者”小队，那么任何一个在 set1 里的点，因为它有边连出去，而边又只能连向 set0 的点，所以它一定被 set0 里的某个守护者覆盖了！喵~
- 同理，如果我们选择 set1，那么所有 set0 里的点也都会被覆盖。
满足数量限制：题目要求我们选的顶点数不能超过 ⌊n/2⌋。我们有两个选择：set0 和 set1。因为 set0 和 set1 的大小加起来正好是总顶点数 n (|set0| + |set1| = n)，所以根据鸽巢原理，这两个集合中至少有一个的大小是小于或等于 n/2 的。我们只要选择那个更小的集合就好啦！它的大小必然满足 ≤ ⌊n/2⌋ 的要求。

所以，最终的策略就是：BFS染色 -> 分成奇偶深度两个集合 -> 输出那个更小的集合！完美解决，喵~

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    // 加速输入输出，让程序跑得像猫一样快，喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t; // 有 t 组测试数据要处理呢
    while (t--) {
        int n, m;
        cin >> n >> m; // n 个点, m 条边
        
        // 用邻接表来存图，adj[i] 存的是和顶点 i 相连的所有顶点
        vector<vector<int>> adj(n + 1);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        // depth 数组用来记录每个点到起点的距离（深度），-1 表示还没访问过
        vector<int> depth(n + 1, -1);
        // BFS 使用的队列
        queue<int> q;

        // 从 1 号点开始我们的染色（BFS）之旅！
        depth[1] = 0; // 1号点深度为0（偶数）
        q.push(1);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            // 遍历 u 的所有邻居 v
            for (int v : adj[u]) {
                // 如果 v 还没被访问过（也就是还没被染色）
                if (depth[v] == -1) {
                    // 那么 v 的深度就是 u 的深度 + 1
                    depth[v] = depth[u] + 1;
                    q.push(v); // 把 v 加入队列，等待探索它的邻居
                }
            }
        }

        // 准备两个篮子，一个放偶数深度的点，一个放奇数深度的点
        vector<int> set0, set1;
        for (int i = 1; i <= n; i++) {
            if (depth[i] % 2 == 0) {
                set0.push_back(i); // 偶数深度的点放入 set0
            } else {
                set1.push_back(i); // 奇数深度的点放入 set1
            }
        }

        // 比较哪个篮子里的点少，就选哪个作为我们的“守护者”小队
        if (set0.size() <= set1.size()) {
            cout << set0.size() << '\n';
            for (int i = 0; i < set0.size(); i++) {
                if (i) cout << ' ';
                cout << set0[i];
            }
            cout << '\n';
        } else {
            cout << set1.size() << '\n';
            for (int i = 0; i < set1.size(); i++) {
                if (i) cout << ' ';
                cout << set1[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N + M) 的说。其中 N 是顶点数，M 是边数。我们的 BFS 算法会访问每个顶点和每条边恰好一次，这是非常高效的！之后遍历所有顶点进行分组也只需要 O(N) 的时间。所以总的时间复杂度就是 O(N + M) 啦。
空间复杂度: O(N + M) 的说。我们主要需要空间来存储邻接表 adj，它的大小是 O(N + M)。此外，depth 数组和 BFS 的队列 q 最多需要 O(N) 的空间。所以总的空间开销也是 O(N + M) 级别。

知识点与总结喵~

这道题真是一道伪装得很好的图论基础题呢！它教会了我们：

二分图染色: 这是解决问题的核心思想。通过将图的顶点分成两个互不相连的集合，我们可以巧妙地解决覆盖问题。
BFS的应用: BFS 不仅可以找无权图的最短路，还是进行二分图染色的完美工具。它逐层遍历的特性天然地将顶点按距离分层，从而区分出奇偶集合。
构造性思维: 有时候，题目不要求找到最优解，而只是要求找到一个可行解。这时，我们可以尝试用一些构造性的方法，比如染色、划分集合等，来直接构建出一个满足条件的答案。
鸽巢原理: |set0| + |set1| = n 这个简单的等式，配合鸽巢原理，是我们能保证答案数量 ≤ ⌊n/2⌋ 的关键！

希望这篇题解能帮到你，主人！以后遇到类似的图论问题，记得想想能不能用染色魔法来解决哦！继续加油，你超棒的，喵~！

E. Cover it! - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路 - 染色魔法时间！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵~ ​