本文创建于 240525，于 251104 从笔记中进行迁移补充，让🌱长成了🌼。

并查集介绍

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。每棵树的根结点的值，代表着一个集合。

并查集支持两种操作：

查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合。
合并（Unite）：合并两个元素所属集合（合并对应的树）。判断两个元素是否同属于一个集合，只需要分别找出它们的根节点，比较根节点是否相同即可。

应用：

图的 Kruskal 算法，判断两个顶点是否同属于一个集合（加入这条边是否形成回路）
判断无向图连通性

基本操作即解释

我们可以把集合比喻成帮派，而代表元素（树的根结点）则是帮主。一开始（并查集初始化阶段），所有大侠各自为战。他们各自的帮主自然就是自己。对于只有一个元素的集合，代表元素自然是唯一的那个元素。

每个人互相比拼，谁输了就认谁为帮主。比如下图展示了当前只剩两个帮派：

假设两个帮派中，2 号和 6 号需要比武，那么他们各自派出帮主，即 1 和 4，进行比武。输的那一方认赢的那一方为帮主。假设 1 号为赢家，那么 4 号带领的帮派将认 1 号为帮主。

整个过程就展示了并查集查找根结点（Find，即找帮主）以及集合合并（Unite，帮派打架）的基本过程。

并查集的存储结构为一个父指针数组 fa。fa[i] 的值为 v 表示编号为 i 的元素的父结点为 v。

初始化方式：

public static int[] fa[MAXN];
public static void init(int n){
	for(int i=1;i<=n;i++){
		fa[i] = i; // 所有结点的帮主就是他自己
	}
}

查询：

// 无路径优化
public static int find(int x){
	return fa[x] == x ? x : find(fa[x]); // 不断向上找根结点的过程
}

合并：

1
2
3

public static void merge(int i, int j){
	fa[find(i)] = find(j); // 将谁设置为父结点不重要
}

路径优化

在并查集结点合并的过程中，我们可能会合成一条很长很长的链。这会导致以后在使用 find 函数时的时间效率不高。

未做路径优化的并查集在最坏情况下的高度为 $O(n)$ ，时间复杂度 $O(n)$ 。

解决方法为，在递归查询的过程中，退栈时，顺带把找到的根结点结果传回给递归链路中的结点：

// 路径压缩
public static int find(int x){
	return fa[x] == x ? x : (fa[x] = find(fa[x]));
}

如果只使用路径压缩的查找方法，并不意味着任何时刻每一棵树的最大深度为 1，即每一个树不一定就是一朵「菊花」。

启发式合并

除了在查找过程中尝试进行路径压缩，我们还可以在合并过程中优化效率。

合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将：

节点较少的树连到另一棵
深度较小的树连到另一棵

具体实现可看后文代码。

相关题目

🟨 P3367 【模板】并查集 - 洛谷

使用了路径压缩 + 启发式合并（结点数）。不使用启发式合并也可以过。注意，使用 Java 语言时需要写一些技巧性的输出输出方式（详看站内文章Java 在 ACM 模式下的输入输出）。

import java.util.*;
import java.io.*;
public class Main {
    public static int[] fa ;
    public static int[] size;
    public static void init(int n) {
        fa = new int[n+1];
        size = new int[n+1];
        Arrays.fill(size,1);
        for (int i = 0; i <= n; i++) {
            fa[i] = i;
        }
    }

    public static int find(int x) {
        int res = fa[x] == x ? x : (fa[x] = find(fa[x]));
        return res;
    }

    public static void merge(int i,int j){
        int x = find(i);
        int y = find(j);
        if(x==y)return;
        if(size[x]<size[y]){
            fa[x] = y;
            size[y]+=size[x];
        }else{
            fa[y] = x;
            size[x]+=size[y];
        }
    }

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int m = nextInt();
        init(n);
        for(int i=0;i<m;i++){
            int z = nextInt();
            int x = nextInt();
            int y = nextInt();
            if(z==1){
                merge(x,y);
            }else{
                boolean b = find(x) == find(y);
                if(b)os.println("Y");
                else os.println("N");
            }
        }
        os.flush();
    }

    static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter os = new PrintWriter(System.out);

    static int nextInt() throws IOException {
        sc.nextToken();
        return (int) sc.nval;
    }
    
    static long nextLong() throws IOException {
        sc.nextToken();
        return (long) sc.nval;
    }
}