前言
一、引例
二、结合引例写出并查集
- 1. 并查集维护一个数组
- 2. 并查集的并操作
- 3. 并查集的查操作
- 4. 基本并查集模板代码实现——第一版（有错误后面分析）
- 5. 一个错误
- 6. 基本并查集模板代码实现——第二版（解决错误）
- 7. 一点点解释，为什么无需在意谁是谁的爸爸
三、并查集的优化
- 1. 并查集优化原理
- 2. 基本并查集模板代码实现——第三版（优化）
四、例题

前言

并查集算法适用于处理一些不相交集合的合并及查询问题。对于这一类的问题使用并查集，不但节省了空间，而且大大缩短了运行时间。
基本的并查集很好写出一个模板，对于一些特殊的题目也能很好对并查集进行变形，接下来来看一下引例了解一下并查集

一、引例

男生寝室关系错综复杂，甚至一个四人寝室都能整出四个爸爸四个儿子。
有一天宿管阿姨想知道这个寝室楼里有多少个爸爸家族，但是宿管只知道哪两个人互称爸爸。
简单易懂的并查集算法以及并查集实战演练
上图是宿管阿姨花了三天三夜整理的爸爸关系图，宿舍楼里总共有n个男生，所以她将每个男生编号0~(n-1)。刚开始人不多，所以阿姨想看0和6是不是一个家族的，只需要看这几个关系即可知道0和6是一个爸爸家族的

后来学生知道了，纷纷来宿管这儿查关系，想看看自己有多少个儿子，自己和隔壁班的学霸是不是爸爸关系。
这一下可给宿管忙坏了，有时候得追溯到十几个人才能确定两个人有爸爸关系，而且还会查错走不少弯路，于是阿姨花了一个晚上，硬生生把关系无向图给画出来了，这下子学生一看图就能知道自己在爸爸家族有多少儿子。

时间一长，学生跑来和宿管讲：“阿姨阿姨，我又有新儿子了，我是0，我儿子是7”，于是阿姨在图上简单地画一下，一个新关系图出来了

二、结合引例写出并查集

1. 并查集维护一个数组

说来你可能不信，以上就是并查集的思路了！下面我们回归正题，在上面例子中，我们涉及到了两个操作，一个是查找，一个是合并，这也是并查集名字的由来。

在这里我们新建一个数组arr，图示第一行为坐标i，第二行为数组元素的内容arr[i]，数组坐标就是学生的编号，分别是0, 1, 2, …, n-1。arr[x]的值表示编号为x的同学的爸爸是谁。初始值表示自己就是自己的爸爸，所以arr[x]=x。

2. 并查集的并操作

接下来一个“父子关系”加入了，0说3是儿子，3说0是儿子，谁也争持不下，那就偷偷的规定右边是左边的爸爸，不告诉他们。（你可能会疑惑，为什么要这样规定，可以反过来吗？后面会做出解释，你姑且先放一边哈）

接下来循环往复，重复以上操作，依次将2与5，4与6合并

我们通过对数组元素的修改，得到了一个集合，我们可以用无向图来表示。按照0的爸爸是3，3的爸爸是4，4的爸爸是6等这样来把它们连起来

3. 并查集的查操作

我们要查找0和4是不是一个家族的，就需要查看0的祖先和4的祖先是同一个人吗？换句话说也就是只需要向上依次查询0的爸爸的爸爸的爸爸，查询4的爸爸的爸爸的爸爸，直到最后的爸爸的爸爸是他自己，就说明这个是爸爸家族里的祖先。下面给出图示说明

做出一点解释，对于第一步，因为数组arr对应的arr[x]=y，表示编号为x的人的爸爸是y，所以要想知道x的父亲，必须访问arr[x]即可知道
对于第二步，祖先一定满足arr[x]=x，即爸爸的爸爸是自己，所以只要不满足arr[x]=x的，一定x一定还有爷爷，这时候就要一直向上查询x的爷爷爷爷爷爷爷爷，直到第六步所示，arr[6]=6表示6是祖先！我们找到了！！

4. 基本并查集模板代码实现——第一版（有错误后面分析）

这样一来，我们简单地得到了第一版的并查集：

/**
 * @author 太白
 */
public class UnionFind {
    private int[] arr;
    public UnionFind(int size) {
        arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = i;		// 初始化，每个人是自己的父亲，即每个人都是祖先
        }
    }

    public int find(int son) {
        int father = arr[son];
        // 循环，直到爸爸的爸爸是自己为止
        while (father != arr[father]) {
        	father = arr[father];
       	}
        return father;
    }
    
    public void union(int son1, int son2) {
    	// 此处有错误，可以思考一下，下面我们举例说明为什么错了
        arr[son1] = son2;	// 合并，son1的爸爸是son2
    }
}

5. 一个错误

我们给出一种情况，我们加了一个新关系，0的爸爸是2，来看看我们现在的代码是否能完成预期功能

完蛋！由于我们在union方法中只是进行arr[son1]=son2;导致原先的祖爷爷6少了一个孙子0，孙子0归祖爷爷5去了，简直是背盟败约，跑到了别的爸爸家族里面去了！！！
没事，其实解决方法特别简单！别被这个小错误给乱了阵脚，这也是起初学该算法容易犯的错误，可以注意一下。
我们维护的是m个爸爸家族，所以如果我们将整个爸爸家族当做是一个人，另一个爸爸家族当做是另一个人，再让这两个巨大的人互认爸爸儿子即可。自然，我们肯定会让祖爷爷出面，去和另一个家族比拼，谁赢了就谁当爸爸。（当然无所谓谁当，后面会解释）

6. 基本并查集模板代码实现——第二版（解决错误）

现在，我们给出第二版，解决了上述的BUG，你会看到解决方式是如此的简单，代码也很好理解，找到双方的祖先，最后让son2的祖先当son1祖先的爸爸。

/**
 * @author 太白
 */
public class UnionFind {
    private int[] arr;
    public UnionFind(int size) {
        arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = i;
        }
    }

    public int find(int son) {
        int father = arr[son];
        while (father != arr[father]) {
        	father = arr[father];
        }
        return father;
    }
    
    public void union(int son1, int son2) {
    	// 请相信我，只改动了这里，其他地方都没有修改过
        int father1 = find(son1);
        int father2 = find(son2);
        // 注意中括号里面的son改成了father
        arr[father1] = father2;
    }
}

7. 一点点解释，为什么无需在意谁是谁的爸爸

在上面我们的代码中默认了都是son1的爸爸是son2，那我们可以让son2的爸爸是son1吗？答案是可以！
因为我们维护的是集合，只是确认一个集合里有谁即可。
从语义上讲：今天你是我爸爸，明天我是你爸爸，但是我们依然是一个爸爸家族里的一员，所以不需要在意谁是谁的爸爸。
从家族结构来讲：整个家族就是一个无向图，关系是双向的。0可以是3的爸爸，3也可以是0的爸爸，所以无需刻意要求，当然也可以在代码里反着写arr[father2]=father1

三、并查集的优化

1. 并查集优化原理

可以看到我们每次查询都得一个一个向上查，0的爸爸是3，3的爸爸是4，4的爸爸是6，6的爸爸是6…如果我们数据量大一点，一个宿舍楼上万人，那么我们每次查询最大可能得查上万次，这太花时间啦！那么我们能不能做出一点改进呢？诶你别说，还真有~
思路是这样的，毕竟我们每次都得查询x的祖先是谁，不关心x的爸爸是谁，x的爷爷是谁，那为什么不直接让arr[x]指向它的祖先编号y呢，在本例中我们为什么不让arr[0]=6, arr[3]=6, arr[4]=6呢？
所以我们在本例中，可以让0、3、4的爸爸直接认定为6即可。延续上一次的查找，我们再多一项功能就是再次遍历0的爸爸3、4，让3和4的爸爸设置为6

2. 基本并查集模板代码实现——第三版（优化）

代码实现也很简单，我们只需要在find方法中加个四五行即可

/**
 * @author 太白
 */
public class UnionFind {
    private int[] arr;
    public UnionFind(int size) {
        arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = i;
        }
    }

    public int find(int son) {
        int father = arr[son];
        while (father != arr[father]) {
        	father = arr[father];
        }
        // 直到循环到祖先为止
        while (father != arr[son]) {
            // 保存当前son的爸爸
            // 因为要更改son的爸爸，所以要有个备份
            int next = arr[son];
            // 将son的爸爸改成father
            arr[son] = father;
            // 找到下一个爸爸（用备份的爸爸赋值给son即可）
            // 将son改成下一个爸爸，为下一个循环做准备
            son = next;
        }
        return father;
    }

    public void union(int son1, int son2) {
        int father1 = find(son1);
        int father2 = find(son2);
        arr[father1] = father2;
    }
}

于是，我们的模板就算是做好了，我习惯在里面添加两个方法，一个是isFamily(int, int)，另一个是getCategory()，第一个可以检测两个人是不是同一个爸爸家族的成员，另外一个看看总共有多少个爸爸家族，这两个方法经常在题目中用到，也很好实现，所以后续我们会结合例题，看如何十分简单地运用该算法解决一些相对复杂的题目。

四、例题

未完待续…

前言