1.概论

定义：
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

主要构成：
并查集主要构成，存储的pre[]，查找函数find（），合并函数join（）。
数组 pre[ ] 记录了每个点的前驱节点是谁，函数 find(x) 用于查找指定节点 x 属于哪个集合，函数 join(x,y) 用于合并两个节点 x 和 y 。

作用：
并查集的主要作用是求连通分支数（如果一个图中所有点都存在可达关系（直接或间接相连），则此图的连通分支数为1；如果此图有两大子图各自全部可达，则此图的连通分支数为2……），求树是否有闭合回路。

find（）函数

定义一个数组int pre[1000];这个数组记录了每个元素的前驱结点是谁。比如说pre[16]=6就表示16号元素的前驱结点是6号。如果一个元素的前驱结点就是他自己，那说明他就是代表元了，查找到此结束。也有一个元素自及组成一个集合的，那么这个集合的代表元就是自己。

int find(int x)                    //查找x的代表元
{
    while(pre[x] != x)            //如果x的前驱结点不是自己
        x = pre[x];
    return x;
}

join（）函数

用来合并两个不相同的树。

void join(int x,int y)                     
{
    int fx=find(x), fy=find(y); 
    if(fx != fy) 
        pre[fx]=fy;    //fy做fx的前驱结点
}

find（）函数优化

这里并没有明确谁是谁的前驱的规则，而是我直接指定后面的数据作为前面数据的前驱。那么这样就导致了最终的树状结构无法预计，即有可能是良好的 n 叉树，也有可能是单支树结构（一字长蛇形）。试想，如果最后真的形成单支树结构，那么它的效率就会及其低下（树的深度过深，那么查询过程就必然耗时）。
而我们最理想的情况就是所有人的直接上级都是头结点，这样一来整个树的结构就只有两级，此时查询结点只需要一次。因此，这就产生了路径压缩算法。
实现：
基于这样的思路，我们可以通过递归的方法来逐层修改返回时的某个节点的直接前驱（即pre[x]的值）。简单说来就是将x到根节点路径上的所有点的pre（上级）都设为根节点。下面给出具体的实现代码：

int find(int x)                     //查找结点 x的根结点 
{
    if(pre[x] == x) return x;        //递归出口：x的上级为 x本身，即 x为根结点        
    return pre[x] = find(pre[x]);    //此代码相当于先找到根结点 rootx，然后pre[x]=rootx 
}