目录
并查集概述
并查集是一种树型的数据结构，由于处理一些不相交集合的合并及查询问题。
并查集思想是用一个数组表示了整片森林，树的根节点唯一是一个集合的标识，我们只要找到了某个元素的树确定它在哪个集合里。
如图（主干就是根节点，枝干就是子节点）：
并查集一般要处理的问题
- 合并：将若干点合并到一个或多个集合（构成的一颗树或多棵树），将多个集合合并（多棵树合并为一棵树）；
- 查询：询问某2个点是否在同一个集合中；
- 其他：计算共有多少个集合（多少棵树）。
并查集的实现方法
（1）举例说明
假设有如下8个点：1 2 3 4 5 6 7 8，假设如下两两的结点在一个集合中，通过并查集构建过程的模拟来看最终有几个集合，并理解并查集的构建过程和查询过程。
两两在一个集合中的节点有：
1 3
1 2
5 4
2 4
6 8
8 7
如图：
（2）数据结构的实现
实际操作时，我们会使用一个点来代表整个集合，就是一个元素的根节点（可以理解为父亲）。
实现方法：
我们要建立一个数组 f[ ] 表示一个并查集，f[i] 表示 i 的父节点。
- 初始化：一开始每一个节点都是一个集合，因此自己的父节点就是自己 f[i]=i （毕竟之后是要合并的）。
- 查询：每一个节点不断地寻找自己的父节点，若此时自己的父节点就是自己，那么该点为集合的根节点，随后返回该点。
- 合并：合并两个集合只需要合并两个集合的根节点，即f[RootA]=RootB，其中RootA，RootB是两个元素的根节点。
- 路径压缩：大多数情况下，在查询过程中只关心根节点是什么，并不关心这棵树的形态。因此我们可以再查询操作的时候将访问过的每个点都指向根节点，这样的方法叫做路径压缩。
如图：
初始化模板：
for(int i=1;i<=n;i++) f[i]=i;//只是模板，切勿直接运行基本查询模板：求x的根：
int find(int x){
return f[x]==x?x:find(f[x]);//三位运算符(不会的话，切勿使用！！！)
/*
if(f[x]==x) return x;
else return f[x]=find(f[x]);
（上面是三位运算符的正常版（新手用））
*/
}路径压缩查询模板：
return f[x]==x?x:find(f[x]);//三位运算符(不会的话，切勿使用！！！)
/*
if(f[x]==x) return x;
else return f[x]=find(f[x]);
（上面是三位运算符的正常版（新手用））
*/合并模板：先判断x和y是否在同一个集合：
void merge(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy) f[fx]=fy;
}注意：合并与查询是亲兄弟，要一起用呦！！！
最后（求看）
最后，现在我们就学完了并查集，并查集其实并不难，难的是要写太多字了！！！以上是作者本人自己总结。我还要说的是：看官们在学习后要趁热打铁做一份笔记呦（有利于加深理解）。
最后的最后：
我收到的评论有点少，希望看官们有时间能多评论指教一下我，谢谢了！！！
制作不易，点个赞吧！！！
制作不易，点个赞吧！！！
制作不易，点个赞吧！！！
