关于并查集我不是直接接触的，而是通过克鲁斯卡尔算法粗略地学习的……挺惭愧……这里我推荐一个我入门时候看到的博客http://blog.csdn.net/dellaserss/article/details/7724401/点击打开链接
主体结构就是一个一维数组而已，我习惯用pre，数组中的内容是记录每一个点的父亲节点在哪里。
比如，下标为2的元素是4（pre[2]==4），就说明序号为2的点的父亲节点的序号是4.
并查集所要维护的东西是树。
并查集的主要函数有：Find函数，作用是找到这个点的祖宗节点；unite函数，作用是连接两个点所在的树；init函数，初始化pre函数（这个初始化是必要的）。
作为初学者，我对unite函数是有一些讨论的，也就是对合并的方式有所注意，因为有很多种树的合并方式。
一开始unite我写的是这样子：
void unite(int a,int b) { int x=Find(a); int y=Find(b); if(x!=y) pre[x]=y; }而Find函数就是很朴素的找祖宗
int Find(int x) { int r=x; while(r!=pre[r]) r=pre[r]; return r; }并没有做路径的压缩。
在这里我想提一点，如果不是以一定的大小顺序输入相连数据的话，pre[x]=y和pre[y]=x没有很大的实质性的差别，因为谁也不知道x和y谁大，所以当Find函数没有路径压缩时，这两种写法无所谓。
另外一点就是当一个点的父亲节点就是他自己时，这个点就是这棵树的根节点（祖宗节点）。（即pre[r]==r的时候）
我们发现，unite这个函数只是把一棵树A的祖宗节点连到了另一个树B的祖宗节点上，而并没有把A的所有的子节点都直接连到B树的祖宗节点上，这样在寻找A树叶子的祖宗节点时会浪费不少的时间，因为要一个父亲节点一个父亲节点地去找。
我们何不直接把A的所有子节点都直接连到B树的祖宗节点上来呢？（也就是路径压缩）
因为最终是求森林中有几棵树，所以进行上面的操作和最终结果没有差别，而且还能省时间。
要怎么做呢？
在Find函数这里做手脚。
这个Find函数可以进行路径压缩的优化的。
int Find(int x) { if(pre[x]!=x) pre[x]=Find(pre[x]); else return pre[x]; }我开始不怎么理解，我们可以先把pre[x]=Find(pre[x])中的前面的pre[x]=去掉，这样只要pre[x]!=x那么Find函数会一直找下去，找到根，带着根的值return，这时我们把pre[x]加上去。那么这个函数就顺带着把x的所有的父节点的父节点都变成了根，也就完成了路径压缩的任务。（注意路劲压缩不是在两棵树合并时候进行的，而是在同一棵树上找根时候进行的。）
具体的题目有很多就举一个例子好了HDU 1213，毕竟是并查集裸题。
AC代码：
#include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; const int maxn=1e3+10; int N,M; int pre[maxn]; void init() { for(int i=1;i<=N;i++) pre[i]=i; } int Find(int x) { if(pre[x]!=x) pre[x]=Find(pre[x]); else return pre[x]; } void unite(int a,int b) { int x=Find(a); int y=Find(b); pre[y]=x; } int main() { int T; scanf("%d",&T); while(T--) { int t1,t2; scanf("%d%d",&N,&M); init(); for(int i=1;i<=M;i++) { scanf("%d%d",&t1,&t2); unite(t1,t2); } int ans=0; for(int i=1;i<=N;i++) if(i==pre[i]) ans++; printf("%d\n",ans); } }
