并查集主要用于处理一些集合的查询及合并问题。比如在《三国演义》中，关羽要和张飞单挑，单挑之前他们需要查询是否是同一阵营的，关羽的老大是刘备，张飞的老大也是刘备，所以他们是同一阵营的，不会打起来。如果关羽要和徐晃单挑，因为关羽的老大是刘备，而徐晃的老大是曹操，他们不是同一阵营的，所以他俩最终会打起来，这个查找老大的过程就是查询。而赵云自从离开公孙瓒之后就飘泊江湖，突然有一天刺杀裴元绍后遇到了刘备，就对刘备说，以后我就跟你混吧，刘备大喜，于是赵云就带着他的本部兵马全部投靠了刘备，这就叫合并。
并查集的使用
自从赵云投靠了刘备之后，赵云以及他手下士兵的老大就都变成了刘备。我们画个图来看下赵云和它的本部兵马是怎么投靠刘备的，如下图所示。
刚开始的时候每个人都是一个单独的个体，他们都是自己的老大，只不过在不断的打斗以及投靠中慢慢的就会发生合并，如下图所示。
并查集的常见方法如下：
public class UnionFind {
public UnionFind(int n);// 构造函数。
private int[] parent; // 记录每个元素的老大。
public int find(int x); // 查找元素x的老大。
// 判断两个元素是否连在一起。
public boolean isConnected(int x, int y);
// 把两个元素连接一起。
public boolean union(int x, int y);
// 连通量的个数。
public int count();
}
上面的代码很简单，就几个函数，都有注释这里就不在一一介绍。刚开始的时候每个人谁也不认识谁，他们都是自己的老大，所以初始化的时候每个元素的老大都不同的，我们来看下构造函数。
private int[] parent; // 记录每个元素的老大。
private int count;// 总的老大数量。
// 构造函数。
public UnionFind(int n) {
count = n;
// 创建一个长度为n的数组。
parent = new int[n];
// 刚开始的时候数组的每个元素都创建一个不同的值，表示自己是自己的老大。
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
这里着重说明一下数组 parent 的含义，假如每一个士兵都有自己的编号，那么 parent[5]=6 就表示编号为 5 的士兵，他的老大就是编号为 6 的那个人。在看一下查找，就更简单了，直接返回他的 parent 即可。
public int find(int x) {
return parent[x];// 返回元素x的parent。
}
假如关羽要和赵云单挑，单挑之前需要判断他们的老大是否是同一个人。
// 是否连接只需要判断他们的老大是否是同一个人就可以了。
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
我们再来看下赵云是怎么投靠刘备的，当赵云投靠刘备之后，他的属下也都要跟着投靠刘备，因为之前赵云属下的老大是赵云，所以这里要改成刘备，我们需要遍历数组，把那些士兵的老大改成刘备。
// 把两个元素连接一起，让他们成为同一阵营。
public boolean union(int x, int y) {
// 如果他们的老大是同一个人，说明他们是同一阵营的，就不需要在合并了。
if (isConnected(x, y))
return false;
// 查找这两个元素的老大。
int xParent = find(x);
int yParent = find(y);
// 这里会合并，假设x是赵云，y是刘备，下面在数组中查找，老大只要
// 是赵云的就都让他们的老大变成刘备。
for (int i = 0; i < parent.length; i++) {
if (parent[i] == xParent)
parent[i] = yParent;
}
count--;// 合并之后总的老大数量减1。
return true;// 合并成功返回true。
}
来看一下完整代码：
public class UnionFind {
private int[] parent; // 记录每个元素的老大。
private int count;// 总的老大数量。
// 构造函数。
public UnionFind(int n) {
count = n;
// 创建一个长度为n的数组。
parent = new int[n];
// 刚开始的时候数组的每个元素都创建一个不同的值。
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
return parent[x];// 返回元素x的老大。
}
// 是否连接只需要判断他们的老大是否是同一个人就可以了。
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
// 把两个元素连接一起，让他们成为同一阵营。
public boolean union(int x, int y) {
if (isConnected(x, y))
return false;
int xParent = find(x);
int yParent = find(y);
for (int i = 0; i < parent.length; i++) {
if (parent[i] == xParent)
parent[i] = yParent;
}
count--;// 合并之后总的老大数量减1。
return true;
}
public int count() {
return count;
}
}
并查集优化
我们看上面的 union 函数，当赵云投靠刘备的时候需要把数组全部遍历一遍，让赵云手下的老大都变成刘备。如果只有赵云一个人投靠还能忍受，但是后面马超也来投靠刘备了，他本部兵马的老大也都要改成刘备，魏延也来投靠了，黄忠也来了，严颜，张松……，这样每来一波人投靠，都需要遍历整个数组，显然效率是很差的，如下图所示。
这时候刘备就说了，你们每来一波人我都要亲自接待，然后告诉他们我是他们的老大，这样太麻烦了，时间都被占用了，还怎样复兴汉室。你们投靠我的时候，只有你们这些老大投靠我就行了，你们的那些士兵原来在谁的手下现在还在谁的手下，如下图所示。
这个时候周仓想要单挑赵云，周仓查了下他的老大是关羽，关羽上面还有老大，是刘备，刘备上面没有老大了，所以周仓的终极老大就是刘备，而赵云查了下他的老大也是刘备，所以他们是同一阵营的，就不在单挑了。我们看下代码，这里只需要看下 find 和 union 方法即可，其他的都是一样的。
// 把两个元素连接一起
public boolean union(int x, int y) {
if (isConnected(x, y))
return false;
int xParent = find(x);
int yParent = find(y);
parent[xParent] = yParent;
count--;
return true;
}
// 查找终极老大，一直往上找。
public int find(int x) {
while (x != parent[x])
x = parent[x];
return x;
}
并查集路径压缩
刘备手下有关羽，关羽手下有周仓，周仓手下还有士兵 …… ，假设往下总共有 100 层上下级关系，最下层的两个士兵要单挑，单挑之前他们需要查一下他们是否是同一阵营的，如下图所示。
查询的时候只能问自己的上级，然后上级在问他的上级……，一直查询到刘备，然后在往下传递，其实就是个递归。因为上下层级关系太多，好不容易查完了，等会又来个士兵 3 要和 士兵 1 单挑，这个时候士兵 1 还要查，显然效率很差，因为之前都查过，所以我们可以把这些曾经查过的路径上所有士兵的老大都标注为刘备，如下图所示。
这样画并不是说关羽和他们是平级的关系，而是说关羽和他们的终极老大都是刘备。所以在查找的时候可以使用递归的方式，往上进行查找，查找到之后在往下逐个传递，告诉他们终极老大是刘备，只需要修改一下 find 方法即可，其他的可以不用动。
// 查找终极老大。
public int find(int x) {
// 注意这里使用的是递归的方式，如果x不是终极老大就一直
// 往上查，查到之后递归往下走，顺便把他们的老大都改成终极老大。
if (x != parent[x])
parent[x] = find(parent[x]);// 递归往回走的时候赋值，如果看不懂可以先看下递归章节。
// 返回终极老大。
return parent[x];
}
按大小合并优化
上面是查找，这里在来看下合并。假设有元素 1,2,3,4,5 他们要合并，那么合并就会有多种方式，我们来看其中的一种，如下图所示。
上面这种合并方式都退化成一个链表了，查询效率当然不会高，一般情况下我们希望他变成一棵树，并且这棵树的高度要尽可能的矮。大家可能会想除了根节点以外，其他的全部都让他变成叶子节点，也就是树只有两层，这样查询效率不就高了。其实这就相当于我们最开始讲的那样，合并的时候效率会很差。关于两棵树合并，这里有两种方式，一种是按大小合并 ，一种是按秩合并 。先来看一下按大小合并，比如下面两棵树要合并，如下图所示。
这种合并坚持的是少数服从多数的原则，节点多的终极老大就会成为合并之后所有节点的终极老大，来看下代码：
public class UnionFind {
private int[] parent; // 记录每个元素的老大。
private int[] range; //每一组元素的个数，合并的时候用到。
private int count;// 总的parent数量。
// 构造函数。
public UnionFind(int n) {
count = n;
// 创建一个长度为n的数组。
parent = new int[n];
range = new int[n];
// 刚开始的时候数组的每个元素都创建一个不同的值。
for (int i = 0; i < n; i++) {
parent[i] = i;
range[i] = 1;// 注意这里初始化是1。
}
}
// 查找终极老大。
public int find(int x) {
if (x != parent[x])
parent[x] = find(parent[x]);
return parent[x];
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
// 把两个元素连接一起，让他们成为同一阵营。
public boolean union(int x, int y) {
if (isConnected(x, y))
return false;
// 查找这两个元素的老大。
int xParent = find(x);
int yParent = find(y);
// 少数服从多数，元素少的合并到元素多的。
if (range[xParent] < range[yParent]) {
// 合并的时候节点个数也需要更新，这里只需要更新终极老大的节点个数就行了，
// 子节点的不需要更新，因为判断是否连通是根据终极老大来判断的。
range[yParent] += range[xParent];
parent[xParent] = yParent;
} else {
range[xParent] += range[yParent];
parent[yParent] = xParent;
}
count--;
return true;
}
public int getCount() {
return count;
}
}
按秩合并优化
再来看下按秩合并，按秩合并可以把它看做是按照树的高度来合并，合并的原理如下：
- 只有一个节点的树，他的秩为 0 ；
- 当两棵不同秩的树合并的时候，秩小的树要合并到秩大的树下面，所以新的树的秩没有改变。
- 当两棵相同秩的树合并的时候，无论谁合并到谁下面都是可以的，但新树的秩是原来树的秩加 1 。
细心的同学可能发现了，这种合并并不能保证合并之后的结果是最优的，因为合并之前需要先查找，而在查找的时候会有路径压缩，可能秩最大的那棵树由于查找变成秩最小的那棵树了，但我们还是把另一棵树放到了他的下面，所以按秩合并是尝试合并出最矮的树，但并不保证一定最矮，我们来看下代码：
public class UnionFind {
private int[] parent; // 记录每个元素的老大。
private int[] height; // 类似于树的高度。
private int count;// 总的parent数量。
// 构造函数。
public UnionFind(int n) {
count = n;
// 创建一个长度为n的数组。
parent = new int[n];
height = new int[n];
// 刚开始的时候数组的每个元素都创建一个不同的值。
for (int i = 0; i < n; i++) {
parent[i] = i;
height[i] = 1;// 注意这里初始化是1。
}
}
// 查找终极老大。
public int find(int x) {
if (x != parent[x])
parent[x] = find(parent[x]);
return parent[x];
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
public boolean union(int x, int y) {
if (isConnected(x, y))
return false;
int xParent = find(x);
int yParent = find(y);
// 矮的合并到高的下面。
if (height[xParent] < height[yParent]) {
parent[xParent] = yParent;
} else if (height[xParent] < height[yParent]) {
parent[yParent] = xParent;
} else {
// 这两棵树一样高，哪个当老大都可以，但要记得当老大的
// 根节点高度要加1。
parent[yParent] = xParent;
height[xParent]++;
}
count--;
return true;
}
public int getCount() {
return count;
}
}
