我的算法书 - 种类并查集

一句话算法

种类并查集给每个元素开一个“反面身份”，用合并同类和反类来维护对立关系。

问题模型

有 $n$ 个元素，每条约束表示两个元素必须属于不同类别。问这些约束是否冲突。

这和判断图是否为二分图是同一个模型：

元素是点；
“不同类”关系是边；
如果出现奇环，就无法分成两类。

核心直觉

普通并查集只能表达“同类”。

为了表达“不同类”，给每个点 $x$ 再开一个反面身份：

x       表示 x 所在类别
x + n   表示 x 的相反类别

如果题目告诉我们 x 和 y 不同类，那么可以推出：

x 和 y 的反面 同类；
x 的反面 和 y 同类。

所以执行：

cpp

        1
2

        unite(x, y + n);
unite(x + n, y);

如果在加入这条关系前，已经发现 x 和 y 同类，就产生冲突。

算法步骤

建立大小为 2 * n 的并查集。
对每条“x 与 y 不同类”的约束：
- 如果 same(x, y)，说明冲突；
- 合并 x 与 y+n；
- 合并 x+n 与 y。
所有约束处理完仍无冲突，则关系一致。

算法证明

核心不变量：对每个元素 $x$ ，x+n 表示与 $x$ 相反的类别；并查集中的同一集合表示“必须同类”。

约束翻译正确

若 $x$ 与 $y$ 不同类，则 $x$ 必须与 $y$ 的反类同类， $x$ 的反类也必须与 $y$ 同类。
冲突判断正确

如果加入“ $x$ 与 $y$ 不同类”前，x 和 y 已在同一集合，则已有约束要求它们同类，新约束要求它们不同类，矛盾。
传递关系正确

并查集会自动传递所有同类关系。反集建模把不同类关系也转成同类合并，所以后续冲突能被 same 检出。

因此种类并查集能正确判断二元对立关系是否一致。

复杂度分析

设元素数为 $n$ ，关系数为 $m$ 。

时间复杂度： $O(m\alpha(n))$ 。
空间复杂度： $O(n)$ ，实际开 2n 个并查集节点。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

        #include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> fa, sz;

    DSU(int n = 0) {
        init(n);
    }

    void init(int n) {
        fa.resize(n + 1);
        sz.assign(n + 1, 1);
        iota(fa.begin(), fa.end(), 0);
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void unite(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) return;

        if (sz[fx] < sz[fy]) swap(fx, fy);
        fa[fy] = fx;
        sz[fx] += sz[fy];
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    DSU dsu(2 * n);
    auto enemy = [n](int x) {
        return x + n;
    };

    bool ok = true;
    while (m--) {
        int x, y;
        cin >> x >> y;

        // x 与 y 必须在不同类别中。
        if (dsu.same(x, y)) {
            ok = false;
        }
        dsu.unite(x, enemy(y));
        dsu.unite(enemy(x), y);
    }

    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

测试用例

输入：

输出：

NO

解释：三个人两两不同类，需要三种类别，但模型只有两类，所以冲突。

应用分类详解

种类并查集的本质是：把“不同类”这种二元对立关系，转成并查集能维护的“同类”关系。

一、二分图在线判定

典型模式： 不断加入“两个点必须不同色”的边，判断当前约束是否还能二染色。
识别信号： 题面出现“分成两组”“两端不能同组”“是否存在奇环”。
核心建模： 每个点开正反两个身份。边 $(x,y)$ 表示 x 和 y+n 同类，x+n 和 y 同类；若 x 和 y 已同类，则出现奇环。

应用场景	经典题目	核心思路
二分图动态加边	二分图判定变体	每条边表示两端点颜色相反
奇环冲突检测	常见图染色题	`same(x,y)` 时说明新边强迫同色点异色
性别关系判定	poj-2492	每条关系表示两个个体必须不同类

二、敌对关系与分组约束

典型模式： 人、动物、任务必须分到两个阵营，某些关系要求两者不能同组。
识别信号： 出现“敌人”“不能关在一起”“互斥”“两类阵营”。
核心建模： 敌人的敌人可以同组，所以把“敌对”转成反集之间的合并。

应用场景	经典题目	核心思路
关押罪犯	luogu-P1525	按冲突值从大到小加入敌对关系，第一次冲突就是答案
两组任务安排	分组可行性题	任务冲突边要求两端进入不同集合
社交敌友关系	敌人的敌人模型	反集维护敌对传递

三、带权或离线的对立关系

典型模式： 约束有强弱顺序，要找最早冲突、最大可满足前缀或最小不可满足阈值。
识别信号： 出现“最大怨气”“按权值排序”“前若干条约束是否可行”。
核心建模： 外层排序或二分答案，内层用种类并查集检查一批二元对立关系是否一致。

应用场景	经典题目	核心思路
最大冲突阈值	luogu-P1525	降序处理边，冲突时当前权值不可避免
可满足前缀	约束一致性题	二分前缀长度，用种类并查集判定
离线加边判矛盾	分批关系检查	每批关系重建 DSU 或回滚 DSU

经典例题

1. luogu-P1525

关押罪犯。敌对关系要求两人分到不同监狱，可以用种类并查集维护冲突。

2. poj-2492

A Bug’s Life。给出若干异性关系，判断是否存在冲突。

3. 二分图判定

如果图是在线加边，且每条边表示两端点不同色，可以用种类并查集动态维护是否出现奇环。