基本的并查集
并查集，一种用于管理元素所属集合的数据结构，形如一片森林，同一棵树内的元素所属同一集合，不同树内的元素不属于同一集合。
将并查集拆分一下。并，合并；查，查询；集，处理的是集合相关内容。
所以并查集一共有两种操作：合并两元素对应集合、查询某元素所属集合(查询它所在树的树根)。
对于每个元素，需要记录它的父亲，用于寻找树根。
如果需要的话，可以记录它的子树大小，一般只有树根需要记录。
初始化
初始时，每个元素都是一棵树，它们自然没有父亲。
如果要记录子树大小的话，则需把它们初始都赋值为 \(1\)。
查询
当我们要查询一个元素 \(x\) 所属集合时，我们需要一路往上跳，直到跳到 \(x\) 所属树的树根，这个元素也就是 \(x\) 所属的集合。
int Find (int x) { // 查询 x 所属集合
return (fa[x] ? Find(fa[x]) : x); // 如果当前节点还有父亲节点，那么就往上跳，否则返回当前节点
}
合并
假如现在要合并两个元素 \(x,y\) 的所属集合，那么只要先找到两棵树的树根，再任选一个点连向另一点即可。
如果仅仅是告诉你两个元素 \(x,y\) 所属同一集合，那么还需判断 \(x,y\) 是否所属不同集合，否则可能会导致死递归。
void merge (int x, int y) { // 合并 x, y 所属集合
x = Find(x), y = Find(y); // 找到树根
if (x != y) { // 只有 x, y 所属不同集合时才能合并
fa[x] = y; // 连接
}
}
并查集时间复杂度优化
合并的复杂度在于查询，除了查询以外只用 \(O(1)\)，那么查询的复杂度呢？
很明显，我们可以利用合并构造出一种形如链状的并查集，那么在查询时复杂度仍然可以达到 \(O(n)\)，并没有达到优化的效果。
那么就要提到合并和查询的优化了。
路径压缩
路径压缩，顾名思义就是把一长条路径给压缩，从而降低时间。
int Find (int x) { // 查询 x 所属集合
return (fa[x] ? fa[x] = Find(fa[x]) : x); // 如果当前节点还有父亲节点，那么就往上跳，否则返回当前节点
// 路径压缩，每次往上跳时都把 fa[x] 更新为树根。
}
启发式合并
当合并两个集合时，集合的大小会影响到后续操作，为了在一定程度上优化时间复杂度，可以选择把节点数少的集合连向节点数多的集合，也可以把深度较小的集合连向深度较大的集合。
// 按节点数启发式合并
void merge (int x, int y) { // 合并 x, y 所属集合
x = Find(x), y = Find(y); // 找到树根
if (x != y) { // 只有 x, y 所属不同集合时才能合并
if (sz[x] > sz[y]) { // 启发式合并
swap(x, y);
}
fa[x] = y, sz[y] += sz[x]; // 连接
}
}
时间复杂度比较玄学，可以自行 bdfs 或者参考 OI-wiki。
一般来说路径压缩后的并查集已经不怕 T，但是启发式合并 + 路径压缩后是 \(O(\alpha(n)\times n)\)，其中 \(\alpha(n)\) 为反阿克曼函数，是一个增长十分缓慢的函数，一般题目里可以将 \(\alpha(n)\) 视为 \(5\) 左右的一个常数，是完全不可能 T 的。
带权并查集
就是在维护普通并查集的同时维护每个节点连接向它的父亲的边权，路径压缩时记得要更新为一段路径的边权。
种类并查集
不要问我为啥没有 OI-wiki Link，因为 OI-wiki 里甚至没有这玩意。
与普通并查集十分相像，主要就是把一个元素分为几个类，可以直接开多个并查集维护。
在这道题里，由于不确定每个动物的种类，则将其分类讨论，分为三类，处理时多一点细节。
标签：查集,合并,查询,集合,所属,Find From： https://www.cnblogs.com/wnsyou-blog/p/17746357.html