这是本文档旧的修订版！
格式：
- 按秩合并的均摊复杂度为 $O(\log n)$
- 单纯使用路径压缩的（总共）复杂度为 $O(n+f(1+\log_{2+f/n}n))$。只有同时使用按秩合并和路径压缩才达到单次 $O(\alpha(n))$
- 使用 $\log$
- 变量使用 $n$，$\text{fa}$ 等，不要直接写
内容：
- 并查集中通常使用“按秩合并”这一术语，建议使用
- 合并部分的代码，建议写成这样，简洁一些
x=find(x),y=find(y); if(x==y) return; if(m[x]>m[y]) std::swap(x,y) m[y]+=m[x]; fa[x]=y;
- 查找部分的代码，建议写成这样，简洁一些
return fa[u] == u ? u : (fa[u] = find(fa[u]));
- 挑几道题出来讲讲呗，不要只放链接
并查集
前言
并查集应用广泛，用于判断元素是否属于同一个集合以及合并集合。
复杂度
最坏到 $O(n)$，单独使用路径压缩或按秩合并可达到 $O(log{n})$，两者同时使用可以达到 $O(\alpha (n))$，其中 $\alpha (n)$ 是阿克曼函数的反函数，可以认为非常小（这部分参照网上）。按秩合并即每次将小的集合合并到大的集合中去，可以减少修改次数。
概念
每个集合有一个代表元素，每一个元素通过一个数组记录其所属集合的代表元素。判断两个元素是否属于同一个集合时查询它们的代表元素是否相同，合并集合时将一个集合的代表元素更替为另一个集合的代表元素。
操作
初始化
每一个元素的代表元素是它自身，每一个元素的高度是0（高度在合并时用到）。用了 $fa$ 数组表示代表元素，$m$ 表示集合元素个数。
合并
这里把合并放到查询前面，有助于理解（也许），用到的 $find$ 函数就是查找代表元素的意思。把一个集合的代表元素更替为零一个集合的代表元素，这里体现为将这个代表元素的 $fa$ 更换为另一个代表元素，以后再进行其他元素 $fa$ 的更迭，有 lazy_tag 的感觉。这里将高度小的合并到高度大的里面去，从而减少了以后更改的工作量。
查找
查找元素的代表元素。根据上面的合并的过程，查找的方式就是递归查找 $fa[x]$ 的 $fa$ 的 $fa$ 的 $fa$······直某个元素的 $fa$ 是它自己。在这里用了一个叫路径压缩的方法，即在查询过程中顺带将所有涉及到的祖辈元素的 $fa$ 都改成集合的代表元素，这样只更新了用到的点，并且为后来的操作提供了便利。
权值
元素与代表元素之间的联系可以带有权值，这样代表元素相同的两个元素可以通过各自与代表元素之间的权值来判断关系。比如负负得正
可持久化
有一些问题要求回溯到之前的某一个版本进行查询或修改，这个时候就要求我们的并查集可持久化。
这个地方的前置知识点就是主席树。因为主席树只支持单点修改，在可持久化的版本里我们就不能使用路径压缩了，因此我们要尽量减少在某一个版本中查询代表元素的时间的话就应当仍然使用启发式合并。
具体的操作就是用主席树把 $fa$ 数组和 $m$ 数组存起来，每一次查询或更改的时候先找一下这个值对应的版本里的位置。
代码就不贴了，就是主席树和并查集的结合。
