算法之并查集

并查集，顾名思义，就是合并不同的集合，并查集是一种集合合并和查找算法。这是一种思想很奇妙的算法，学会它，在你后续的程序学习中可以有很多的可以用的地方。

什么是并查集？

举个栗子来更好的理解一下什么是并查集。球球大作战大家应该都玩过吧，我们对这个游戏做一个修改，只能大球碰到小球可以把小球吃掉，小球可以融合到打球的内部。那么问题来了，初始化有n个小球，经过不断的战斗，第i个小球当前是在谁的身上？

从上面的图中，大家可以看出来，通过3轮的pk，最终1，2，3，8最终都被4号吃掉了，5，7被6号吃掉了。并查集的主要作用就是用来判断当前第i个球球最终是在谁身上。上图对应的并查集如下：

通过上面的图片，大家很容易就可以看到3号球球是被4号球球吃掉了。

并查集的构建和查找

构建并查集

我们通过数组P来记录不同球球的父节点。

int P[];

初始状态下，每个球球都是自己的父亲，所以P的值为：

for (int i = 1; i <= 8; i++) {
	P[i] = i;
}
P: [1  2  3  4  5  6  7  8]

第一轮结束后，2号的父亲变成了1号，3号的父亲变成了4号…

P[2] = P[1];  // P[1]代表1号的父节点，当前还是1号
P[3] = P[4];  // P[4]代表4号的父节点，当前还是4号
P[5] = P[6];
P[7] = P[6];

old p: [1  2  3  4  5  6  7  8]
new P: [1  1  4  4  6  6  6  8]

第二轮：

P[8] = P[4];

old P: [1  1  4  4  6  6  6  8]
new P: [1  1  4  4  6  6  6  4]

第三轮：

P[1] = P[4];

old P: [1  1  4  4  6  6  6  4]
new P: [4  1  4  4  6  6  6  4]

查找并查集

我们来查找2号目前被谁吃掉了

P[2] ： 1  // 找到2号的第一个父节点是1号，继续查找1号的父节点
P[1] :  4  // 1号的父节点是4号，继续查找4号的父节点
P[4] :  4  // 4号的父节点就是自己，此时再继续查找下去也没有什么意义了，所以，可以返回当前2号的根节点是4号

代码实现：

通过上面的实例，我们已经发现规律了：
1、初始化：自己初始化为自己的根节点
2、当两个元素合A,B并的时候，只需要找到这两个元素的根节点 find(A)，find(B)， 然后将其中一个作为另一个的父节点即可,即：P[find(A)] = find(B) 或者 P[find(B)] = find(A)。
代码如下:

int P[N]; // 存储每个元素的父节点，N代表最大值

// 初始化编号
for (int i = 1; i <= n; i ++ ) {
	p[i] = i;
}

// 查找当前元素的根节点，父节点的父节点的父节点的父节点......，结束条件是当前节点和父节点相同的时候，则为根节点
int find(int x)
{
    if (P[x] != x) {
    	P[x] = find(P[x]);
    }
    return P[x];
}

// 合并a和b两个元素所在的集合：
P[find(a)] = find(b); // 或者 P[find(b)] = find(a)

回忆杀

到此为止我们的并查集的介绍就结束了，回顾一下：

1、当你回忆并查集的时候，想一下球球大作战，大球球吃掉小球球，最终构成不同的集合
2、那怎么查找某个初始的球球当前在哪个大球球的身上呢？想起我们的并查集图片（第二张图)
3、根据图片，我们来归纳父节点数组P[]的形成过程，从而得出并查集合并的逻辑：P[find(a)] = find(b)
4、构建完成 后如何查找根节点？父节点的父节点的父节点的父节点......，结束条件是当前节点和父节点相同的时候，则为根节点