代码随想录冲冲冲 Day53 图论Part5

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

首先并查集主要是

1.将两个元素添加到一个集合当中

2.判断两个元素是不是在一个同一个集合中

对比起一个二维数组 在添加和查询时必须要进行完全的遍历

在几个元素是不是在一个集合中时，

可以通过给出A元素，就可以通过 father[A] = B，father[B] = C，找到根为 C。

给出B元素，就可以通过 father[B] = C，找到根也为为 C，说明 A 和 B 是在同一个集合里。

但是这样的话 就会有一个深度大速度慢的情况 由于我们只需要找到共同根

所以可以使用 路径压缩 的方法。

我们只需要在递归的过程中，让 father[u] 接住 递归函数 find(father[u]) 的返回结果。

因为 find 函数向上寻找根节点，father[u] 表述 u 的父节点，那么让 father[u] 直接获取 find函数 返回的根节点，这样就让节点 u 的父节点 变成根节点。

下方是代码模板

107. 寻找存在的路径

这个完全是上面的应用 基本上一模一样