一.介绍说明

1.什么是并查集

并查集（Disjoint-Set，也称为不相交集合或 Union-Find 数据结构）是一种用于处理集合合并与查询等操作的数据结构。它通常被用来维护一组元素，这些元素被划分成若干个不相交的集合，每个集合具有一个代表元素，通常是集合中的一个元素。

并查集支持以下两种主要操作：

1. 合并（Union）： 将两个不相交的集合合并为一个集合。这意味着两个集合的代表元素会变成同一个，并且它们的元素都属于同一个集合。

2. 查找（Find）： 查找一个元素所属的集合，通常返回该集合的代表元素。这个操作通常用于判断两个元素是否属于同一个集合。

并查集的一个关键特性是，它以非常高效的方式支持这两种操作。通常，这是通过树结构来实现的，其中每个集合都是一棵树，树的根节点是代表元素。这些树可以很高效地合并（通过将一棵树的根节点连接到另一棵树的根节点）以及查找（通过遵循树的父指针链路找到根节点）。

并查集广泛用于解决各种问题，包括连通性问题、划分问题、最小生成树算法中的 Kruskal 算法等。它是一个重要的数据结构，用于高效地管理和操作不相交集合。常见的并查集实现包括基于树结构的普通并查集和基于树结构的优化版本，如按秩合并和路径压缩。这些优化可以进一步提高并查集的性能。

2.并查集模版

以下是一个简单的并查集的 Java 模板，包括基本的合并和查找操作，以及按秩合并和路径压缩的优化：

class UnionFind {
    private int[] parent; // 用于存储每个元素的父节点
    private int[] rank; // 用于记录树的深度（秩）

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];

        // 初始化，每个元素的父节点是它自己，秩为0
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // 查找操作（Find）
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并操作（Union）
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 按秩合并，将深度较小的树合并到深度较大的树下面
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

使用上述模板，你可以创建一个并查集对象，并使用它执行合并和查找操作。例如：

UnionFind uf = new UnionFind(5); // 创建一个包含5个元素的并查集

uf.union(0, 1); // 合并元素0和元素1所在的集合
uf.union(2, 3); // 合并元素2和元素3所在的集合

boolean isConnected = uf.find(0) == uf.find(1); // 检查元素0和元素1是否属于同一个集合，应返回true

这是一个基本的并查集模板，你可以根据需要进行扩展和修改，以适应具体问题的要求。

二.具体实现

1.基础实现

public class DisjointSet {
    int[] s;
    // 索引对应顶点
    // 元素是用来表示与之有关系的顶点
    /*
        索引  0  1  2  3  4  5  6
        元素 [0, 1, 2, 3, 4, 5, 6] 表示一开始顶点直接没有联系（只与自己有联系）

    */

    public DisjointSet(int size) {
        s = new int[size];
        for (int i = 0; i < size; i++) {
            s[i] = i;
        }
    }

    // find 是找到老大
    public int find(int x) {
        if (x == s[x]) {
            return x;
        }
        return find(s[x]);
    }

    // union 是让两个集合“相交”，即选出新老大，x、y 是原老大索引
    public void union(int x, int y) {
        s[y] = x;
    }

    @Override
    public String toString() {
        return Arrays.toString(s);
    }

}

2.路径压缩

public int find(int x) { // x = 2
    if (x == s[x]) {
        return x;
    }
    return s[x] = find(s[x]); // 0    s[2]=0
}

3.按秩合并

Union By Size

public class DisjointSetUnionBySize {
    int[] s;// 用于存储每个元素的父节点
    int[] size;//用于记录树的深度（秩）
    public DisjointSetUnionBySize(int size) {
        s = new int[size];
        this.size = new int[size];
        for (int i = 0; i < size; i++) {
            s[i] = i;
            this.size[i] = 1;
        }
    }

    // find 是找到老大 - 优化：路径压缩
    public int find(int x) { // x = 2
        if (x == s[x]) {
            return x;
        }
        return s[x] = find(s[x]); // 0    s[2]=0
    }

    // union 是让两个集合“相交”，即选出新老大，x、y 是原老大索引
    public void union(int x, int y) {
//        s[y] = x;
        if (size[x] < size[y]) {
            int t = x;
            x = y;
            y = t;
        }
        s[y] = x;
        size[x] = size[x] + size[y];
    }

    @Override
    public String toString() {
        return "内容："+Arrays.toString(s) + "\n大小：" + Arrays.toString(size);
    }

    public static void main(String[] args) {
        DisjointSetUnionBySize set = new DisjointSetUnionBySize(5);

        set.union(1, 2);
        set.union(3, 4);
        set.union(1, 3);
        System.out.println(set);
    }
}