并查集

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的 合并 及 查询 问题。 它支持两种操作：

• 查找（Find）：确定某个元素处于哪个子集；
• 合并（Union）：将两个子集合并成一个集合。

并查集表示的是元素间的「同类」关系，每个元素的类别由其在树中祖先表示。树通常就用数组实现，而因为平坦的树结构更利于查询，可以用路径压缩的办法实现find。

经典实现

int find(int x) {
    if (x != fa[x])  // x不是自身的父亲，即x不是该集合的代表
        fa[x] = find(fa[x]);  // 查找x的祖先直到找到代表,于是顺手路径压缩
    return fa[x];
}

void unionSet(int x, int y) {
    x = find(x);
    y = find(y);
    fa[x] = y;  // 把x的祖先变成y的祖先的儿子
}

参考

• P2024 食物链 : 这道题目是用了三倍大小的并查集，来表示除了「同类」关系外的「猎物」和「天敌」关系。类似的，可以通过增加并查集大小来表示更多的集合关系。
• P1197 星球大战 在某些情况下如果需要并查集的删除操作，可以通过反向操作，即视为加点来求解