Java算法数据结构基础并查集模版 [洛谷-P3367]

题目地址

题目描述

输入输出样例

并查集模版

介绍

1. 路径压缩（Path Compression）

2. 按秩合并（Union by Rank / Size）

代码讲解

操作讲解

时间复杂度分析

应用场景

题目地址

【模板】并查集 - 洛谷

题目描述

输入输出样例

并查集模版

class UnionFind {
    private int[] parent; // 存储每个元素的父节点
    private int[] size;   // 存储每个集合的大小，用于按秩合并

    // 初始化并查集
    public UnionFind(int n) {
        parent = new int[n + 1]; // 因为编号从 1 到 N，所以数组大小是 N+1
        size = new int[n + 1];   // 存储每个集合的大小
        for (int i = 1; i <= n; i++) {
            parent[i] = i;  // 每个元素的父节点初始为自己
            size[i] = 1;    // 每个元素的初始大小为 1
        }
    }

    // 查找元素 x 所在的集合，带路径压缩优化
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩：将父节点直接指向根节点
        }
        return parent[x];  // 返回根节点（集合的代表）
    }

    // 合并两个集合，带按秩合并优化
    public void union(int x, int y) {
        int rootX = find(x);  // 查找 x 的根节点
        int rootY = find(y);  // 查找 y 的根节点

        if (rootX != rootY) {  // 如果根节点不同，说明它们不在同一个集合
            // 按秩合并：较小的集合合并到较大的集合
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];  // 更新根节点的大小
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];  // 更新根节点的大小
            }
        }
    }

    // 判断 x 和 y 是否在同一个集合中
    public boolean connected(int x, int y) {
        return find(x) == find(y);  // 如果两个元素的根节点相同，说明在同一个集合中
    }
}

介绍

并查集（Union-Find）是一种数据结构，主要用于处理一些不交集的合并及查询问题，特别是在图论中用来解决连通性问题。并查集支持两种基本操作：

查找（Find）：判断某个元素属于哪个集合，返回该集合的代表元素（根）。
合并（Union）：将两个集合合并成一个集合。

并查集通过 路径压缩 和 按秩合并 来优化效率，减少操作的时间复杂度。

1. 路径压缩（Path Compression）

路径压缩是一种优化查找操作的方法。在查找过程中，我们不仅仅返回当前元素的根节点，还将当前节点的父节点直接指向根节点，这样可以加速以后的查找操作。也就是说，当你调用 find(x) 时，你将 x 的祖先节点都直接连接到根节点。

2. 按秩合并（Union by Rank / Size）

按秩合并是一种优化合并操作的方法，旨在确保树的深度（或大小）尽可能小。在合并两个集合时，较小的集合（树）会被合并到较大的集合（树）上。这样，最终形成的树的深度会较小，从而提高查找操作的效率。

代码讲解

java


复制代码
class UnionFind {
    private int[] parent; // 存储每个元素的父节点
    private int[] size;   // 存储每个集合的大小，用于按秩合并

    // 初始化并查集
    public UnionFind(int n) {
        parent = new int[n + 1]; // 因为编号从 1 到 N，所以数组大小是 N+1
        size = new int[n + 1];   // 存储每个集合的大小
        for (int i = 1; i <= n; i++) {
            parent[i] = i;  // 每个元素的父节点初始为自己
            size[i] = 1;    // 每个元素的初始大小为 1
        }
    }

    // 查找元素 x 所在的集合，带路径压缩优化
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩：将父节点直接指向根节点
        }
        return parent[x];  // 返回根节点（集合的代表）
    }

    // 合并两个集合，带按秩合并优化
    public void union(int x, int y) {
        int rootX = find(x);  // 查找 x 的根节点
        int rootY = find(y);  // 查找 y 的根节点

        if (rootX != rootY) {  // 如果根节点不同，说明它们不在同一个集合
            // 按秩合并：较小的集合合并到较大的集合
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];  // 更新根节点的大小
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];  // 更新根节点的大小
            }
        }
    }

    // 判断 x 和 y 是否在同一个集合中
    public boolean connected(int x, int y) {
        return find(x) == find(y);  // 如果两个元素的根节点相同，说明在同一个集合中
    }
}