代码随想录第五十五天| 并查集理论基础寻找存在的路径

本文链接：https://blog.csdn.net/Sweeping_Robot/article/details/146255069

并查集理论基础

背景

并查集是一种数据结构，主要用于解决元素的连通性问题。简单来说，当我们需要判断多个元素是否属于同一个集合时，并查集可以高效地完成这一任务。它支持两种基本操作：将两个元素合并到同一个集合中，以及判断两个元素是否属于同一个集合。

原理讲解

并查集的核心思想是通过一个数组来记录每个元素的父节点，从而形成一种树形结构。每个集合用一棵树来表示，树的根节点即为该集合的代表元素。具体来说：

初始化：每个元素最初都是独立的集合，其父节点指向自身。
合并操作：将两个元素所在的集合合并。这通过找到它们各自的根节点，然后将其中一个根节点指向另一个根节点来实现。
查找操作：确定一个元素所属的集合。这通过不断查找该元素的父节点，直到找到根节点为止。

示例

假设我们有元素 A、B、C，初始时每个元素都是独立的集合：

father[A] = A
father[B] = B
father[C] = C

当我们合并 A 和 B 时，将 B 的父节点指向 A：

father[B] = A

此时，A 和 B 属于同一个集合。接下来合并 B 和 C：

首先找到 B 的根节点 A，然后将 C 的父节点指向 A
father[C] = A

现在，A、B、C 都属于同一个集合，其根节点为 A。

路径压缩

路径压缩是一种优化技术，用于减少查找根节点所需的时间。在查找过程中，将每个访问过的节点直接指向根节点，从而扁平化树的结构。这样，后续的查找操作将更加高效。

实现

在查找函数中，通过递归的方式找到根节点，并在返回时将当前节点的父节点直接设置为根节点：

int find(int u) {
    if (u != father[u]) {
        father[u] = find(father[u]); // 路径压缩
    }
    return father[u];
}

代码模板

以下是并查集的基本代码模板：

class UnionFind {
private:
    vector<int> father;

public:
    UnionFind(int n) {
        father.resize(n);
        for (int i = 0; i < n; ++i) {
            father[i] = i; // 初始化，每个元素的父节点指向自身
        }
    }

    int find(int u) {
        if (u != father[u]) {
            father[u] = find(father[u]); // 路径压缩
        }
        return father[u];
    }

    void unite(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            father[rootV] = rootU; // 合并两个集合
        }
    }

    bool isConnected(int u, int v) {
        return find(u) == find(v);
    }
};

常见误区

合并操作的顺序：在合并两个集合时，必须先找到它们的根节点，然后再进行合并。否则可能导致错误的连接关系。
路径压缩的理解：路径压缩并不是在合并操作中进行，而是在查找操作中完成的。每次查找都会优化树的结构，使得后续操作更快。

拓展

除了路径压缩，并查集还可以通过按秩合并来进一步优化。按秩合并是指在合并两个集合时，将高度较小的树合并到高度较大的树上，从而控制树的高度增长。这通常与路径压缩结合使用，以获得更好的性能。

复杂度分析

时间复杂度：在路径压缩优化下，单次查找操作的均摊时间复杂度接近于 O(1)，使得并查集在处理大量元素和操作时非常高效。
空间复杂度：主要取决于存储父节点的数组，空间复杂度为 O(n)，其中 n 是元素的数量。

总结

并查集是一种简单而高效的处理动态连通性问题的数据结构。通过路径压缩和按秩合并等优化技术，它能够在接近常数的时间内完成元素的合并和查找操作。理解并查集的核心思想和优化方法，对于解决许多实际问题（如图的连通性、集合的合并等）具有重要意义。

并查集模板

//并查集模板
class DisJoint{
    private int[] father;
 
    public DisJoint(int N) {
        father = new int[N];
        for (int i = 0; i < N; ++i){
            father[i] = i;
        }
    }
 
    public int find(int n) {
        return n == father[n] ? n : (father[n] = find(father[n]));
    }
 
    public void join (int n, int m) {
        n = find(n);
        m = find(m);
        if (n == m) return;
        father[m] = n;
    }
 
    public boolean isSame(int n, int m){
        n = find(n);
        m = find(m);
        return n == m;
    }
 
}

寻找存在的路径

题目描述

给定一个包含 n 个节点的无向图，节点编号从 1 到 n。判断是否存在一条从节点 source 到节点 destination 的路径。

解题思路

并查集算法

并查集算法是一种高效处理图连通性问题的数据结构，适合判断两个节点是否属于同一连通分量。

初始化：每个节点初始化为独立集合，父节点指向自身。
合并操作：对于图中的每条边，将两个节点所属的集合合并。
查找操作：判断两个节点是否属于同一集合，即查找它们的根节点是否相同。

算法步骤

输入处理：读取节点数 n 和边数 m，以及 m 条边。
并查集初始化：创建大小为 n+1 的数组（节点编号从 1 到 n）。
合并边：对每条边的两个节点执行合并操作。
判断连通性：读取源节点和目标节点，判断它们是否属于同一集合。

代码实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int N, M;
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        
        // 创建并查集对象，节点编号从 1 到 N
        DisJoint disJoint = new DisJoint(N + 1);
        
        // 处理每条边，合并节点
        for (int i = 0; i < M; ++i) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            disJoint.join(u, v);
        }
        
        // 读取源节点和目标节点
        int source = scanner.nextInt();
        int destination = scanner.nextInt();
        
        // 判断是否连通
        if (disJoint.isSame(source, destination)) {
            System.out.println("1");
        } else {
            System.out.println("0");
        }
    }
}

// 并查集模板
class DisJoint {
    private int[] father;

    // 构造函数，初始化父节点数组
    public DisJoint(int size) {
        father = new int[size];
        for (int i = 0; i < size; ++i) {
            father[i] = i; // 每个节点初始时指向自身
        }
    }

    // 查找根节点，路径压缩
    public int find(int node) {
        if (father[node] != node) {
            father[node] = find(father[node]); // 递归查找并路径压缩
        }
        return father[node];
    }

    // 合并两个节点所在的集合
    public void join(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            father[rootV] = rootU; // 将一个根节点指向另一个
        }
    }

    // 判断两个节点是否属于同一集合
    public boolean isSame(int u, int v) {
        return find(u) == find(v);
    }
}