并查集

介绍：

此算法主要是用于查找树中的一结点的根结点，通常会用作查找匹配两个节点的根节点是否是同一个。

Java代码模板：

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
35
36
37
38
/**
 * @description: TODO
 * @author 长白崎
 * @date 2023/3/25 16:34
 * @version 1.0
 */

/**
 * 并查集主要作用就是搜索两棵树的父节点是否是同一个节点。
 */
public class Main {

    public static void main(String[] args) {

        //并查集中用于记录每个结点的父节点的数组，数组下标代表的就是对应节点，对应下标数组元素的内容代表的是其父结点。
        int parent[] = new int[100];
        //这一步是必不可少的，这一步是为了初始化并查集的数组，初始状态下每个结点的父结点就是他本身。
        for(int i =0 ; i< parent.length ; ++i) parent[i] =i;
        int point = find(parent,1); //比如这里是查找1的根节点

    }


    //并查集核心查找算法
    public static int find(int parent[],int point){
        while(parent[point]!=point)
            point = parent[point];
        return point;
    }
    
    //带有路径压缩
    public static int find(int parent[],int point){
        if(parent[point]!=point) parent[point] = find(parent[point]);
        return parent[point];
    }

}