【数据结构-图论】并查集

并查集（Union-Find）是一种数据结构，它提供了处理一些不交集的合并及查询问题的高效方法。并查集主要支持两种操作：

查找（Find）：确定某个元素属于哪个子集，这通常意味着找到该子集的“代表元素”或“根元素”。

合并（Union）：将两个子集合并成一个集合。

并查集通过数组或树形结构来实现，其中每个节点指向其父节点，根节点指向自身，这样形成一个或多个树形结构。每棵树代表一个集合，树根的标识符（通常是数组的索引）代表整个集合的标识符。

基本概念：
初始化：开始时，每个元素各自构成一个单元素集合，即每个元素的父节点是其自身。
路径压缩：在执行查找操作时，将查找路径上的每个节点直接连接到根节点，这样可以加快后续查找的速度。
按秩合并：合并时，总是将更小的树连接到更大的树的根节点上，这可以帮助避免树变得过深，从而保持操作的效率。

并查集的重要思想在于，用集合中的一个元素代表集合。

现在1号和3号比武，假设1号赢了（这里具体谁赢暂时不重要），那么3号就认1号作帮主（合并1号和3号所在的集合，1号为代表元素）。

现在2号想和3号比武（合并3号和2号所在的集合），但3号表示，别跟我打，让我帮主来收拾你（合并代表元素）。不妨设这次又是1号赢了，那么2号也认1号做帮主。

上面大概介绍完了整体的东西下面介绍一下细节：

下面是代码部分：

// 查找i的代表元素，并进行路径压缩优化
int find(int i) {
    if (fa[i] == i)  // 如果元素i指向自己，那么它是代表元素
        return i;
    else
        return fa[i] = find(fa[i]);  // 否则递归查找，并更新i的父链接为代表元素
}

// 合并i和j所在的集合
void unionn(int i, int j) {
    int i_fa = find(i);  // 查找i的代表元素
    int j_fa = find(j);  // 查找j的代表元素
    fa[i_fa] = j_fa;     // 将i的集合合并到j的集合中
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

find 函数通过递归查找找到一个元素的代表元素，并在查找的过程中将元素直接链接到代表元素，这个优化叫做路径压缩，它可以减少后续查找的时间。

unionn 函数将两个元素所在的集合合并成一个集合。它首先找到每个元素的代表元素，然后将其中一个集合的代表元素链接到另一个集合的代表元素上，从而完成合并。这里没有实现按秩合并或路径压缩的更复杂的优化。

下面是一道题

public class UnionFind {
    private int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
    
    public static void main(String[] args) {
     
        UnionFind uf = new UnionFind(10);
        uf.union(0, 1); // Marry person 1 and 2
        uf.union(2, 3); // Marry person 3 and 4
        boolean areMarried = uf.isConnected(1, 4); // Check if person 2 and 5 are related
        System.out.println(areMarried ? "YES" : "NO"); // Output should be "NO" if unrelated
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34