使用场景

• 一开始每个元素都有自己的集合，在自己的集合里只有这个元素自己。
• find(i): 查找所在集合的代表元素，代表元素来代表 i 所在的集合。
• bool isSame(a,b): 判断 a、b 是否在同一个集合中。
• void union(a, b): a 所在的集合和 b 所在的集合中所有的元素合并成一个集合。
• 各种操作单词调用的时间复杂度为 O(1)。

实现

这里使用一个father[]来标记每个元素所对应的父节点，相同集合公用一个相同的祖先以便查询。

给出find()的实现：

int find(int i) {
    if (i == f[i])
        return i;
    f[i] = find(f[i]); // 这里可以实现路径压缩，从而优化查询时间
    return f[i];
}

这样，每个相同的集合的元素的父亲元素就是这个集合的祖先元素。直接判断祖先元素的异同，就是isSame()函数。

给出union(a, b)的实现：

int size[];
void union(a, b) {
    if(size[a] > size[b]) {
        int temp = a;
        a = b;
        b = temp;
    }
    f[find(a)] = find(b); // a的祖先的叠是b的祖先
}

种类并查集

定义

将一个集合中的元素根据其不同的关系进行分类和合并。？

🤓☝️

人话：在普通并查集亲戚的亲戚也是亲戚的基础上有着其他关系，并非根据物品的种类来进行分类，而是类似敌人的敌人就是朋友这种微妙的关系。

一般来说，种类并查集不是开多个数组来进行维护，而是扩大并查集数组的规模。

与普通并查集的区别

• 普通并查集维护的是具有连通性、传递性的问题，例如亲戚的亲戚是亲戚，其三者共属于同一集合。

• 种类并查集维护类似敌人的敌人就是朋友这种微妙的关系。

使用时机

当我们不知道哪些具体的元素应该分到一个集合时，我们无法直接构建普通并查集。若我们知道那些元素不能分为一类，我们可以使用种类并查集来构建集合关系。

实现

以敌人的敌人就是朋友为例。

种类并查集的初始化

因为需要维护敌人和朋友两种关系，因此需要初始化两倍大小的并查集。令 1n 为朋友关系，n+12n 为敌人关系。即对于任意一个 i 属于 i~n，均有敌人 i+n，此时这个敌人并不是真是存在的，只是假想出来的，为了分类使用。假设有 4 个认：

1 2 3 4 | 5 6 7 8

合并操作

我们现在知道 1 和 2 是敌人关系，所以自然可以推出 2 和 1 的敌人 1+n 是朋友关系，1 应该和 2 的朋友 2+n 是朋友关系。

此时我们又知道 2 和 4 是敌人关系，所以可以得到 4 和 2 的敌人 2+n 是朋友关系，2 和 4 的敌人 4+n 是朋友关系。

知道谁和谁是朋友关系后所进行的合并操作与普通并查集相同。

贴个链接：P2024 [NOI2001] 食物链