代码随想录 并查集理论基础

一、背景

1.并查集可解决的问题：并查集常用来解决连通性问题。也就是说当我们需要判断两个元素是否在同一个集合里的时候，就想到要用并查集。

2.并查集的功能：

（1）将两个元素添加到一个集合中。

（2）判断两个元素在不在同一个集合。

二、原理：从代码层面上讲，如何将两个元素添加到同一个集合中？

1.错误想法：

（1）放到同一个数组或者set或者map中，这样就表示两个元素在同一个集合（但是这么多元素分门别类，可不止一个集合，可能是成百上千个集合，这时会定义很多的数组，不好实现）。

（2）定义一个二维数组（但是如果要判断两个元素是否在同一个集合的时候，只能把二维数组都遍历一遍；每当想添加一个元素到某集合的时候，依然需要把二维数组都遍历一遍，才知道要放到哪个集合里，代码实现逻辑非常复杂）。

2.正确思路：

（1）将三个元素A,B,C（分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通？只需要用一个一维数组来表示，即：father[A] = B,father[B] = C，这样就能表述A与B与C连通了（有向连通图）。

代码如下所示：

// 将v，u 这条边加入并查集 void join(int u, int v) { u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[v] = u; }

（2）find函数的寻根过程，就是通过数组下标找到数组元素，然后一层一层地寻根，代码如下所示。

// 并查集里寻根的过程 int find(int u) { if (u == father[u]) return u; // 如果根就是自己，直接返回