F. Bipartite Checking - 题解

比赛与标签

比赛: Educational Codeforces Round 22 标签: data structures, dsu, graphs, *2500 难度: *2500

题目大意喵~

主人，你好呀！今天我们来挑战一个非常有趣的图论问题，喵~

是这样的：我们有一个包含 n 个顶点的图，一开始里面空空如也，一条边都没有的说。接下来会有 q 次操作。每次操作会给你两个顶点 u 和 v：

• 如果 u 和 v 之间已经有一条边了，那就把它删掉。
• 如果还没有边，那就给它们之间连上一条。

在每次操作之后，主人都需要判断一下，当前的图是不是一个“二分图”呢？所谓的二分图，就是可以把所有顶点染成两种颜色（比如黑色和白色），并且保证任意一条边的两个端点颜色都不同。如果可以，就输出 "YES"，不然就输出 "NO"，呐。

解题思路 Nyan~

喵呜~ 这个问题看起来有点棘手，因为它不仅有加边操作，还有删边操作。普通的并查集（DSU）很擅长处理加边，但是要撤销操作（删边）就非常麻烦了。

但是主人请看，题目并没有要求我们“在线”回答，也就是说，我们可以先把所有 q 个查询都读进来，再一起处理。这就是“离线”思想，一个非常强大的武器哦！

从“删边”到“生命周期”

既然可以离线，我们就可以换个角度看问题。对于每一条边，它不是被简单地“添加”或“删除”，而是在图里存在了一段“生命周期”。比如，一条边在第 i 次查询时被加上，在第 j 次查询时被删掉，那么它的生命周期就是从查询 i 到查询 j-1 这个时间段，对吧？如果它被加上后一直没有被删掉，那它的生命周期就是从 i 到 q。

这样一来，问题就从“动态的加加减减”变成了“一堆边在不同的时间段内存在”。

时间线段树 + 可撤销并查集 = 完美组合！

为了处理这些带有生命周期的边，我们可以请出一位超级好用的帮手——线段树！不过这次，我们的线段树不是建在顶点上，而是建在**时间（查询编号）**上，从 1 到 q。

线段树的每个节点都代表一个时间区间。对于一条生命周期为 [l, r] 的边，我们就把它“挂”在线段树上所有能完整覆盖 [l, r] 的节点上。这可以通过一个简单的区间更新操作实现，喵~

接下来，我们对这个时间线段树进行一次深度优先搜索（DFS）。

1. 当我们进入一个线段树节点（代表一个时间段）时，我们就把挂在这个节点上的所有边，通过并查集 unite 操作加入到图中。
2. 如果我们走到了叶子节点 [i, i]，这代表我们正处于第 i 次查询的时刻。此时，从根节点到这个叶子节点的路径上所有节点挂着的边，共同构成了第 i 次查询时的图。我们就可以检查这个图是不是二分图啦！
3. 当我们离开一个节点，准备回溯到父节点时，关键的一步来了：我们必须撤销刚刚在这个节点做的所有加边操作，以保证当我们访问兄弟节点时，图的状态是正确的。

这就需要一个支持撤销操作的并查集，也就是 可撤销并查集 (Undoable DSU)！

可撤销并查集如何判断二分图？

普通的并查集加上路径压缩后很难撤销，所以我们这里不能用路径压缩，只用按秩合并（或者按大小合并）。为了记录操作，我们用一个栈（history）来存下每次合并时修改的所有信息（比如谁的 parent 变了，谁的 size 变了）。回溯时，只要从栈里取出记录，恢复原状就好啦！

那怎么用并查集判断二分图呢？我们可以给并查集增加一个 dist 数组！dist[i] 表示节点 i 到它所在连通分量根节点的路径长度的奇偶性（0 或 1）。这可以看作是节点的“颜色”。

• find(i)：在查找根节点的同时，累加路径上的 dist 值（用异或操作），就能得到 i 相对于根节点的“颜色”。
• unite(u, v)：
  • 如果 u 和 v 已经在同一个连通分量里了，我们就检查它们的“颜色”。如果 dist[u] == dist[v]，说明它们颜色相同却要连边，这就形成了一个奇数环！图就不是二分图了。
  • 如果它们不在同一个连通分量，我们就合并它们。假设 v 的根节点要连到 u 的根节点上，那么 v 的根节点的 dist 就要更新为 dist[u] ^ dist[v] ^ 1，以维持正确的颜色关系。

我们再维护一个全局变量 non_bip_count，记录当前有多少个连通分量已经确定不是二分图了。在叶子节点 [i, i]，只要检查 non_bip_count是不是 0，就知道整个图是不是二分图啦！

总结一下我们的喵喵拳法：

1. 离线处理：读入所有查询，用 map 记录每条边最后一次出现的时间，计算出每条边的生命周期 [start, end]。
2. 时间线段树：将每条边根据其生命周期 [start, end]，挂到时间线段树的 O(log q) 个节点上。
3. DFS 遍历：带着一个可撤销并查集，对线段树进行 DFS。
4. 检查与回溯：在叶子节点检查二分性并记录答案，在回溯时利用历史记录栈撤销并查集的操作。

这样，我们就在 O(q * log(q) * α(n)) 的时间内优雅地解决了这个问题，是不是很酷，喵~

代码实现

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>

// 为了方便，我们对顶点和查询都使用1-based索引喵~
const int MAXN = 100005;
const int MAXQ = 100005;

// 定义我们强大的可撤销并查集！
struct DSU {
    int parent[MAXN]; // 记录每个节点的父节点
    int sz[MAXN];     // 记录每个连通分量的大小（用于按大小合并）
    int dist[MAXN];   // 记录节点到根节点路径长度的奇偶性，用于判断二分图
    int is_bip[MAXN]; // 标记每个连通分量是否还是二分图 (1:是, 0:不是)
    int non_bip_count; // 全局计数，有多少个连通分量不是二分图

    // 用来记录修改操作的结构体，方便撤销
    struct Change {
        int* ptr;     // 指向被修改变量的指针
        int old_val;  // 修改前的值
    };
    std::vector<Change> history; // 历史记录栈

    // 初始化n个节点的并查集
    void init(int n) {
        non_bip_count = 0;
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
            sz[i] = 1;
            dist[i] = 0; // 初始时，每个点到自己的距离是0
            is_bip[i] = 1; // 初始时，每个单点连通分量都是二分图
        }
        history.clear();
    }

    // 查找根节点，并返回节点i到根的路径奇偶性
    // 注意：这里没有路径压缩，因为路径压缩很难撤销！
    std::pair<int, int> find(int i) {
        int parity = 0;
        while (i != parent[i]) {
            parity ^= dist[i];
            i = parent[i];
        }
        return {i, parity};
    }

    // 合并u和v所在的集合
    void unite(int u, int v) {
        auto [root_u, parity_u] = find(u);
        auto [root_v, parity_v] = find(v);

        if (root_u != root_v) { // 如果不在同一个集合
            // 按大小合并，小的合并到大的上面
            if (sz[root_u] < sz[root_v]) {
                std::swap(root_u, root_v);
            }
            // 记录所有即将发生的修改！
            history.push_back({&parent[root_v], parent[root_v]});
            parent[root_v] = root_u;
            history.push_back({&sz[root_u], sz[root_u]});
            sz[root_u] += sz[root_v];
            history.push_back({&dist[root_v], dist[root_v]});
            dist[root_v] = parity_u ^ parity_v ^ 1; // 核心！更新新子节点到新根的距离奇偶性

            // 如果两个分量中有一个已经不是二分图了，合并后的大分量也不是
            if (is_bip[root_u] && !is_bip[root_v]) {
                history.push_back({&is_bip[root_u], is_bip[root_u]});
                is_bip[root_u] = 0;
                // non_bip_count 不变，因为总的非二分分量数没变
            } else if (!is_bip[root_u] && !is_bip[root_v]) {
                // 如果两个都是非二分图，合并后非二分图分量数减一
                history.push_back({&non_bip_count, non_bip_count});
                non_bip_count--;
            }

        } else { // 如果已经在同一个集合了
            // 检查是否形成奇数环
            if (parity_u == parity_v) {
                // 如果它们到根的距离奇偶性相同，连边后就会形成奇数环
                if (is_bip[root_u]) { // 如果这个分量之前还是二分图
                    history.push_back({&is_bip[root_u], is_bip[root_u]});
                    is_bip[root_u] = 0; // 现在它不再是了
                    history.push_back({&non_bip_count, non_bip_count});
                    non_bip_count++; // 非二分图分量数加一
                }
            }
        }
    }

    // 撤销操作，恢复到某个快照点
    void backtrack(size_t snapshot_size) {
        while (history.size() > snapshot_size) {
            Change c = history.back();
            *c.ptr = c.old_val; // 恢复旧值
            history.pop_back();
        }
    }
};

int n, q;
// 时间线段树，每个节点存一个边的列表
std::vector<std::pair<int, int>> seg_tree[4 * MAXQ];
bool ans[MAXQ + 1]; // 存储每个查询的答案
DSU dsu;

// 把一条生命周期为[l, r]的边，加入到时间线段树上
void add_edge_to_range(int u, int v, int l, int r, int cur_node, int cur_l, int cur_r) {
    if (l > r || l > cur_r || r < cur_l) {
        return;
    }
    if (l <= cur_l && cur_r <= r) {
        seg_tree[cur_node].push_back({u, v});
        return;
    }
    int mid = cur_l + (cur_r - cur_l) / 2;
    add_edge_to_range(u, v, l, r, 2 * cur_node, cur_l, mid);
    add_edge_to_range(u, v, l, r, 2 * cur_node + 1, mid + 1, cur_r);
}

// DFS遍历时间线段树来求解
void dfs_solve(int cur_node, int cur_l, int cur_r) {
    // 拍个快照！记下当前历史记录栈的大小
    size_t snapshot = dsu.history.size();

    // 将当前时间段的所有边加入并查集
    for (const auto& edge : seg_tree[cur_node]) {
        dsu.unite(edge.first, edge.second);
    }

    if (cur_l == cur_r) { // 到达叶子节点，即某个具体的查询时间点
        ans[cur_l] = (dsu.non_bip_count == 0);
    } else { // 否则，继续向下递归
        int mid = cur_l + (cur_r - cur_l) / 2;
        dfs_solve(2 * cur_node, cur_l, mid);
        dfs_solve(2 * cur_node + 1, mid + 1, cur_r);
    }

    // 回溯！恢复到进入此节点之前的状态
    dsu.backtrack(snapshot);
}

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

    std::cin >> n >> q;

    // 用map来记录每条边最后一次出现的时间点
    std::map<std::pair<int, int>, int> edge_last_appeared;
    for (int i = 1; i <= q; ++i) {
        int u, v;
        std::cin >> u >> v;
        if (u > v) std::swap(u, v); // 保证边的表示唯一
        if (edge_last_appeared.count({u, v})) {
            // 如果边出现过，说明这次是删除操作。它的生命周期就确定了
            add_edge_to_range(u, v, edge_last_appeared[{u, v}], i - 1, 1, 1, q);
            edge_last_appeared.erase({u, v});
        } else {
            // 第一次出现，记录添加时间
            edge_last_appeared[{u, v}] = i;
        }
    }

    // 处理那些到最后都没有被删除的边
    for (const auto& p : edge_last_appeared) {
        add_edge_to_range(p.first.first, p.first.second, p.second, q, 1, 1, q);
    }

    dsu.init(n);
    if (q > 0) {
        dfs_solve(1, 1, q);
    }

    for (int i = 1; i <= q; ++i) {
        if (ans[i]) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度: O(q * log(q) * α(n)) 的说。
  • 我们有 q 次查询，可能会产生 O(q) 条不同的边。
  • 每条边的生命周期 [l, r] 在时间线段树上会被拆分成 O(log q) 个区间。所以，所有边在线段树节点中存储的总数是 O(q * log q)。
  • 我们对线段树进行一次DFS。在每个节点，我们会对挂载的边进行并查集操作。并查集单次操作（没有路径压缩）的时间复杂度是 O(log n)，但由于我们按大小合并，可以优化到 O(α(n))，即反阿克曼函数，一个增长极慢的函数，近似于常数。
  • 所以总的时间复杂度就是 O(q * log(q) * α(n)) 啦！
• 空间复杂度: O(q * log q) 的说。
  • 主要空间开销在于时间线段树。如上所述，所有边在树中总共会存储 O(q * log q) 次。
  • 可撤销并查集里的 history 栈在DFS过程中，深度最大也和边总数有关，是 O(q * log q) 级别。

知识点与总结

主人，这个问题是不是超级有启发性呀？它完美地展示了如何将多种数据结构巧妙地结合起来解决复杂问题，喵~

1. 离线思想：当题目中的修改操作难以撤销，并且不需要强制在线回答时，一定要先想想能不能离线处理！这能把动态问题转化为静态问题，打开新世界的大门。
2. 时间线段树：这是一个非常经典的模型！将操作按时间轴展开，用线段树来管理作用于不同时间区间的事件（比如本题的“边存在”事件）。它和CDQ分治有异曲同工之妙。
3. 可撤销并查集：为了配合时间线段树的DFS回溯，我们需要一个能“反悔”的数据结构。通过记录历史操作来实现撤销，是实现这类数据结构的通用方法。记住，为了方便撤销，通常不能使用路径压缩哦！
4. 并查集与二分图：利用“到根节点距离的奇偶性”来维护颜色信息，是并查集判断二分图（即奇数环）的标准技巧，非常优雅，要记住呐！

这道题是数据结构领域一道非常好的练习题，它能加深对线段树、并查集以及离线算法思想的理解。主人做得很棒，为你鼓掌喵~！