Moe's CF Life

Codeforces 1364D - Ehab's Last Corollary

哈喵~ 这是一道非常有趣的图论构造题。它巧妙地将独立集和找环这两个经典问题结合在了一起，还保证总能找到一个解，真是太神奇了喵！下面就让本猫娘带你一步步解开这道题的秘密吧~

题目大意喵

题目会给我们一个有 $n$ 个点、 $m$ 条边的无向连通图，还有一个整数 $k$ 。我们需要完成下面两个任务中的 任意一个：

找到一个大小恰好为 $\lceil\frac{k}{2}\rceil$ $⌈ \frac{k}{2} ⌉$ 的 独立集。
- 独立集 是指图中的一个点集，其中任意两个点之间都没有边直接相连。就像一群喜欢独处的小猫，互相不打扰喵~
找到一个长度 不超过 $k$ $k$ 的 简单环。
- 简单环 是指环路上的点除了起点和终点相同外，其余各不相同。就像小猫追着自己的尾巴转圈圈，但不会踩到自己第二次脚印。

题目保证，对于任何合法的输入，这两个任务中至少有一个是可以完成的。

解题思路详解喵

这道题的核心思想是利用 深度优先搜索（DFS） 来探索图的结构。DFS就像一只好奇的小猫在迷宫里探险，它会沿着一条路走到黑，直到无路可走再返回换一条路。在探险的过程中，我们可以记录下很多有用的信息，比如每个点的深度 depth 和它在搜索树中的父节点 parent。

让咱们从任意一个点（比如1号点）开始DFS，然后根据找到的信息来决定是输出环还是独立集。

整个过程可以分为三种情况来讨论，喵~

情况一：我们找到一个长度小于等于 k 的环

在DFS的过程中，当我们从点 u 访问它的邻居 v 时：

如果 v 还没有被访问过，那我们就继续往下探索 dfs(v, u, ...)。
如果 v 已经被访问过了，并且 v 不是 u 的父节点，那么恭喜！我们找到了一条 返祖边（Back Edge），这意味着一个环被发现了！

这个环由这条返祖边 (u, v) 和DFS树上从 v 到 u 的路径构成。环的长度就是 depth[u] - depth[v] + 1。

我们可以遍历整张图，找出所有返祖边形成的环中最短的那一个。设这个最短环的长度为 L。如果 L <= k，那么我们就成功解决了任务二！直接输出这个环就好啦，喵~

情况二：图中没有环（它是一棵树）

如果在整个DFS过程中，我们都没有发现任何返祖边，那就说明这个图是一棵树。树是一个非常特殊的图，它有一个很棒的性质：它是一个 二分图。

我们可以根据每个节点在DFS树中的深度是奇数还是偶数，将所有节点分成两个集合：S_even（偶数深度）和 S_odd（奇数深度）。

在同一集合内的任意两个点，都不可能有边相连（因为树上的边总是连接深度差为1的两个点）。
所以，S_even 和 S_odd 都是独立的！它们都是独立集。

根据鸽巢原理，这两个集合中至少有一个的大小不小于 $\frac{n}{2}$ 。因为题目保证 $k \le n$ ，所以 $\lceil\frac{k}{2}\rceil \le \lceil\frac{n}{2}\rceil$ 。这意味着，那个较大的独立集的大小，肯定足够我们取出 $\lceil\frac{k}{2}\rceil$ 个点。所以，我们只要从 S_even 和 S_odd 中选出较大的那个，然后输出其中任意 $\lceil\frac{k}{2}\rceil$ 个点，就解决了任务一，是不是很聪明呀，喵~

情况三：我们找到了环，但最短环的长度 L > k

这是最有趣的一种情况了！我们找到了一个最短环 C，但它的长度 L 太长了，不满足任务二的要求。但是，这个“太长”的环恰恰能帮助我们解决任务一！

思考一下，为什么 C 是最短环？这意味着在环 C 上的任意两个不相邻的顶点之间，都不存在直接的边（我们称之为“弦”）。如果存在这样的弦，那么这条弦就会和环的一部分构成一个更短的环，这与 C 是最短环相矛盾。

既然环上没有弦，那么我们就可以在环上 隔一个点取一个点。比如环是 v1 -> v2 -> v3 -> ... -> vL -> v1，我们取 {v1, v3, v5, ...}。这样取出的点集一定是独立集，因为 v1 只和 v2、vL 相邻，v3 只和 v2、v4 相邻，它们互相之间都不会有边。

这个独立集的大小是 $\lfloor \frac{L}{2} \rfloor$ 。因为我们知道 $L > k$ ，所以这个独立集的大小至少是 $\lfloor \frac{k+1}{2} \rfloor$ 。而 $\lfloor \frac{k+1}{2} \rfloor$ 总是大于等于 $\lceil\frac{k}{2}\rceil$ 的！ (比如 k=5, ceil(k/2)=3, L>=6, floor(L/2)>=3; k=6, ceil(k/2)=3, L>=7, floor(L/2)>=3)

所以，我们只需要在这个最短环上，隔一个点取一个点，凑够 $\lceil\frac{k}{2}\rceil$ 个点，就完美地解决了任务一！

总结一下策略就是：

用DFS找图中的最短环。
如果最短环长度 L <= k，输出这个环。
如果图是树（无环），按深度奇偶性划分成两个独立集，输出较大那个集合中的 $\lceil\frac{k}{2}\rceil$ 个点。
如果最短环长度 L > k，就在这个环上隔一个点取一个点，凑够 $\lceil\frac{k}{2}\rceil$ 个点作为独立集输出。

你看，无论发生什么，我们总能找到一个解，喵~

代码解析喵

这是主人你给我的C++代码，让本猫娘来给你逐行讲解一下吧！

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

const int MAXN = 100005;
std::vector<int> adj[MAXN]; // 邻接表存图
int n, m, k;
int depth[MAXN], parent[MAXN]; // 记录深度和父节点
bool visited[MAXN]; // 访问标记

int min_len = MAXN + 1; // 最短环的长度，初始化为一个很大的值
int cycle_u = -1, cycle_v = -1; // 构成最短环的返祖边的两个端点

// 深度优先搜索函数
void dfs(int u, int p, int d) {
    visited[u] = true;
    parent[u] = p;
    depth[u] = d;

    for (int v : adj[u]) {
        if (v == p) continue; // 跳过父节点
        if (visited[v]) { // 如果邻居v已经被访问过
            // 找到了一个环！
            if (depth[u] > depth[v]) { // 确保是返祖边
                int len = depth[u] - depth[v] + 1;
                if (len < min_len) { // 如果这个环更短
                    min_len = len; // 更新最短环信息
                    cycle_u = u;
                    cycle_v = v;
                }
            }
        } else {
            dfs(v, u, d + 1); // 继续向下探索
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0, 1); // 从节点1开始DFS

    // 对应思路中的情况一: 找到了长度 <= k 的环
    if (cycle_u != -1 && min_len <= k) {
        std::cout << 2 << std::endl;
        std::cout << min_len << std::endl;
        std::vector<int> cycle;
        int curr = cycle_u;
        // 从u回溯到v，找到环路上的点
        while (curr != cycle_v) {
            cycle.push_back(curr);
            curr = parent[curr];
        }
        cycle.push_back(cycle_v);
        std::reverse(cycle.begin(), cycle.end()); // 翻转得到正确的顺序
        for (size_t i = 0; i < cycle.size(); ++i) {
            std::cout << cycle[i] << (i == cycle.size() - 1 ? "" : " ");
        }
        std::cout << std::endl;
    } else {
        // 对应思路中的情况二和三: 输出独立集
        std::cout << 1 << std::endl;
        int needed = (k + 1) / 2; // 这就是 ceil(k/2) 的整数写法

        if (cycle_u != -1) { // 情况三: 最短环长度 > k
            std::vector<int> path;
            int curr = cycle_u;
            // 同样地，先提取出这个环上的所有点
            while (curr != cycle_v) {
                path.push_back(curr);
                curr = parent[curr];
            }
            path.push_back(cycle_v);
            // 隔一个点输出一个，凑够 needed 个
            for (int i = 0; i < needed; ++i) {
                std::cout << path[i * 2] << (i == needed - 1 ? "" : " ");
            }
            std::cout << std::endl;
        } else { // 情况二: 图是树
            std::vector<int> S_even, S_odd;
            // 按深度奇偶性分组
            for (int i = 1; i <= n; ++i) {
                if (depth[i] % 2 == 0) {
                    S_even.push_back(i);
                } else {
                    S_odd.push_back(i);
                }
            }
            // 选择较大的那个集合输出
            if (S_even.size() >= S_odd.size()) {
                for (int i = 0; i < needed; ++i) {
                    std::cout << S_even[i] << (i == needed - 1 ? "" : " ");
                }
                std::cout << std::endl;
            } else {
                for (int i = 0; i < needed; ++i) {
                    std::cout << S_odd[i] << (i == needed - 1 ? "" : " ");
                }
                std::cout << std::endl;
            }
        }
    }

    return 0;
}

Codeforces 1364D - Ehab's Last Corollary ​

题目大意喵 ​

解题思路详解喵 ​

情况一：我们找到一个长度小于等于 k 的环 ​

情况二：图中没有环（它是一棵树） ​

情况三：我们找到了环，但最短环的长度 L > k ​

代码解析喵 ​

相关知识点小课堂喵 ​