一文搞懂并查集

淩亂°似流年 2024-03-02 03:57 14阅读 0赞

#### 一文搞懂并查集 ####

*   *  1 背景意义
     *  2 原理讲解
     *  3 路径压缩
     *  4 代码模板

### 1 背景意义 ###

首先要知道**并查集**可以解决什么问题呢？

*  **并查集**常用来解决 **连通性** 问题。
 *  大白话就是当我们需要判断 **两个元素** 是否在 **同一个集合** 里的时候，我们就要想到用**并查集**。

**并查集**主要有两个功能：

*  将 **两个元素** **添加** 到一个集合中；
 *  **判断** **两个元素** **在不在** 同一个集合。

接下来围绕并查集的这两个功能来展开讲解。

### 2 原理讲解 ###

从代码层面，我们如何将**两个元素** **添加** 到同一个集合中呢？

**举个栗子：**

我们将三个元素 `A`，`B`，`C` （分别是数字）**放在同一个集合**，其实就是将三个元素**连通**在一起，如何连通呢。

*  只需要用一个 **一维数组** 来表示，即：`father[A] = B`，`father[B] = C` 这样就表述 `A`与 `B` 与 `C`连通了（有向连通图）。
 *  `A` 连通 `B`，`A` 是 `索引下标`，根据 `father[A]` 的数值就知道 `A` **连通** `B`

**⭐️ 添加元素代码如下：**

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

那么 **判断** 这三个元素是否在同一个集合里?

*  其实知道 `A` 连通 `B` 就已经足够了，也就是 **寻根** **思路**，只要 `A` ，`B`，`C` 在同一个根下就是同一个集合；
    
     *  给出 `A` 元素，就可以通过 `father[A] = B`，`father[B] = C`，找到根为 `C`。
     *  给出 `B` 元素，就可以通过 `father[B] = C`，找到根也为为 `C`，说明 `A` 和 `B` 是在同一个集合里。

**⭐️ find 函数代码如下：**

// 并查集里寻根的过程
    int find(int u) {
        
        if (u == father[u]) return u; // 如果根就是自己，直接返回
        else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找
    }

如何表示 `C` 也在同一个元素里呢？

*  我们需要 `father[C] = C`，即 `C` 的根也为 `C`，这样就方便表示 `A`，`B`，`C` 都在同一个集合里了。

**⭐️ father数组初始化代码如下：**

// 并查集初始化
    void init() {
        
        for (int i = 0; i < n; ++i) {
        
            father[i] = i;
        }
    }

最后我们如何 **判断** **两个元素**是否在同一个集合里？

*  如果通过 **find函数** 找到 两个元素属于同一个根 的话，那么这两个元素就是同一个集合，

**⭐️ 判断 是否同根函数代码如下：**

// 判断 u 和 v是否找到同一个根
    bool isSame(int u, int v) {
        
        u = find(u);
        v = find(v);
        return u == v;
    }

### 3 路径压缩 ###

在实现 `find` 函数的过程中，我们知道，通过递归的方式，不断获取 `father` 数组下标对应的数值，最终找到这个集合的根。

*  如果这棵多叉树高度很深的话，每次 `find` 函数 去寻找跟的过程就要**递归很多次**；
 *  所以可以将 **非根节点** 的 **所有节点** 直接指向 **根节点**；
 *  在**递归**的过程中，让 `father[u]` 接住 递归函数 `find(father[u])` 的 **返回结果**。

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

**⭐️ 代码如下，注意看注释，路径压缩就一行代码：**

// 并查集里寻根的过程
    int find(int u) {
        
        if (u == father[u]) return u;
        else return father[u] = find(father[u]); // 路径压缩，如果没有找到父节点，会一直更新
    }

以上代码在C++中，可以用**三元表达式**来精简一下，代码如下：

int find(int u) {
        
        return u == father[u] ? u : father[u] = find(father[u]);
    }

### 4 代码模板 ###

综上整理，模板如下

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
    vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
    
    // 并查集初始化
    void init() {
        
        for (int i = 0; i < n; ++i) {
        
            father[i] = i;
        }
    }
    // 并查集里寻根的过程
    int find(int u) {
        
        return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
    }
    
    // 判断 u 和 v是否找到同一个根
    bool isSame(int u, int v) {
        
        u = find(u);
        v = find(v);
        return u == v;
    }
    
    // 将v->u 这条边加入并查集
    void join(int u, int v) {
        
        u = find(u); // 寻找u的根
        v = find(v); // 寻找v的根
        if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        father[v] = u;
    }

通过模板，我们可以知道，**并查集**主要有 三个功能。

1.  **寻找根节点**，函数：`find(int u)`，也就是判断这个节点的祖先节点是哪个；
2.  **将两个节点接入到同一个集合**，函数：`join(int u, int v)`，将两个节点连在同一个根节点上；
3.  **判断两个节点是否在同一个集合**，函数：`isSame(int u, int v)`，就是判断两个节点是不是同一个根节点。

**注：仅供学习参考，如有不足，欢迎指正**！