并查集是一种特殊的集合，它包括“并”和“查”两部分，就是说，它只能进行“并”和“查”两种操作。
小明在玩一个叫做“到底有几个团队”的游戏，这个游戏是这样的：有若干个人组成了若干个团队，然后，这些人会给小明若干个线索，线索类似于说“xx和xx在一个团队里”，小明要做的，就是根据线索求出到底有多少个团队。
比如说：
现在有\(3\)个人，分别是小力，小华和小刚。
这时他们给出了\(1\)条线索：小华和小刚是一个团队的。
很显然，有\(2\)个团队。
但如果再复杂一点呢？
现在有\(10\)个人，分别是\(1,2,3,4,5,6,7,8,9,10\)。
这时他们给出了\(7\)条线索：
\(2\)和\(4\)是一个团队的；
\(5\)和\(7\)是一个团队的；
\(1\)和\(3\)是一个团队的；
\(8\)和\(9\)是一个团队的；
\(1\)和\(2\)是一个团队的；
\(5\)和\(6\)是一个团队的；
\(2\)和\(3\)是一个团队的。
是不是感觉有点晕了，这么多人和线索，而且这些线索绕来绕去的，实在有些难分辨。
当然，我们可以画图来帮助解题。
最初始的状态：
得到线索“\(2\)和\(4\)是一个团队的”时：
得到线索“\(5\)和\(7\)是一个团队的”时：
得到线索“\(1\)和\(3\)是一个团队的”时：
得到线索“\(8\)和\(9\)是一个团队的”时：
得到线索“\(1\)和\(2\)是一个团队的”时：
得到线索“\(5\)和\(6\)是一个团队的”时：
得到线索“\(2\)和\(3\)是一个团队的”时：
因为\(2\)和\(3\)在得到线索“\(1\)和\(3\)是一个团队的”时就在一个团队里了，所以状态没有发生变化。
从图中可知，共有\(4\)个团队。
并查集就类似于模仿上文“画图”的方式来进行问题求解。
上文说到，并查集的操作分为“并”和“查”两部分，我们来讲讲并查集的两种操作的实现。
当题目数据比较特殊，比如是一条链时，这种“并”与“查”的方式就会超时。这时就要用到一种优化的方法：路径压缩。这种做法就是在找完某个元素的根节点之后，在递归回来的时候顺便把路径上元素的父亲都指向根节点。
举个例子：
没有路径压缩的元素存储方式：
有路径压缩的元素存储方式：
从图中可以看出来，有路径压缩的并查集进行“查”的操作会更快。
实现如下(仅能递归实现)：
int find(int x)//"查" { if(father[x]!=x)father[x]=find(father[x]); return father[x]; }注意，最初始的状态是所有元素的父亲就是自己，所以，应当进行初始化。 代码如下：
for(int i=1;i<=n;i++) father[i]=i;看了那么久，我们来做一道题目吧，将例子中的人数设定为\(n(n \le 10000)\)人，将线索设定为\(m(m \le 10000)\)条，线索的输入方式设定为：A B\((A,B\)为数字\()\)现在来做一做吧。
\(Code:\)
#include <iostream> using namespace std; int father[10010];//father数组存储着并查集元素 void start(int n)//初始化 { for(int i=1;i<=n;i++) father[i]=i; } int find(int x)//"查" { if(father[x]!=x)father[x]=find(father[x]); return father[x]; } void unionn(int x,int y)//"并" { x=find(x); y=find(y); father[x]=y; } int main() { int n,m,ans=0; cin>>n>>m; start(n); for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; unionn(a,b);//将a,b合并成一个团队 } for(int i=1;i<=n;i++) if(father[i]==i)ans++;//如果某个元素的父亲就是它自己，则这是一个以其为首的团队 cout<<ans; return 0; }转载于:https://www.cnblogs.com/Naive-Cat/p/10702990.html
相关资源：JAVA上百实例源码以及开源项目