第十一章 图论part05

并查集理论基础

并查集理论基础很重要，明确并查集解决什么问题，代码如何写，对后面做并查集类题目很有帮助。
文章讲解

并查集的 Java 代码模板

import java.util.Arrays;

public class UnionFind {
    private int[] parent;  // 存储每个节点的父节点
    private int n;  // 节点数量

    // 构造函数，初始化并查集
    public UnionFind(int n) {
        this.n = n;
        parent = new int[n];
        init();
    }

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

    // 寻找根节点，带路径压缩
    public int find(int u) {
        if (u == parent[u]) {
            return u;
        } else {
            parent[u] = find(parent[u]);
            return parent[u];
        }
    }

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

    // 将两个节点加入到同一个集合
    public void join(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            parent[rootV] = rootU;
        }
    }

    // 测试用例
    public static void main(String[] args) {
        int n = 1005;  // 根据具体问题确定节点数量
        UnionFind uf = new UnionFind(n);

        // 示例操作
        uf.join(1, 2);
        uf.join(3, 4);
        System.out.println(uf.isSame(1, 2));  // true
        System.out.println(uf.isSame(1, 3));  // false
        uf.join(2, 3);
        System.out.println(uf.isSame(1, 3));  // true
    }
}

代码解释：

1. 初始化 (init)：将每个节点初始化为自身的父节点，表示每个节点开始时都是独立的集合。
2. 寻找根节点 (find)：使用路径压缩技术来加速后续查询。在查找过程中，将访问过的节点直接链接到根节点。
3. 判断是否在同一集合 (isSame)：通过比较两个节点的根节点来判断它们是否在同一个集合中。
4. 将两个节点加入同一集合 (join)：将一个节点的根节点链接到另一个节点的根节点，从而将两个集合合并。

按秩（rank）合并
二刷再看

寻找存在的路径

并查集裸题，学会理论基础后，本题直接可以直接刷过
文章讲解

import java.util.Scanner;

public class Main {

    static private int[] father; // 按照节点大小定义数组大小

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

    // 并查集里寻根的过程
    static public int find(int u) {
        if (u == father[u]) {
            return u;
        } else {
            father[u] = find(father[u]); // 路径压缩
            return father[u];
        }
    }

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

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        init(n);// 初始化并查集

        // 处理每一条边，将其加入并查集
        while (m-- > 0) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            join(s, t);
        }

        // 读取源节点和目标节点
        int source = sc.nextInt();
        int destination = sc.nextInt();

        // 判断源节点和目标节点是否属于同一集合
        if (isSame(source, destination)) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }

    }
}