题目所属分类

并查集

并查集模板

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

原题链接

代码案例：输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No

题解

初始化

for(int i = 0 ; i < n ; i++){ p[i]=i; }

就是将当前数据的父节点指向自己

查找 + 路径压缩

int find(int x){ //返回x的祖先节点 + 路径压缩
    //祖先节点的父节点是自己本身
    if(p[x] != x){
        //将x的父亲置为x父亲的祖先节点,实现路径的压缩
        p[x] = find(p[x]);    
    }
    return p[x]; 
}
1
2
3
4
5
6
7
8
9
10

针对find(1)

find(1) p[1] = 2 p[1] = find(2)
find(2) p[2] = 3 p[2] = find(3)
find(3) p[3] = 4 p[3] = find(4)
find(4) p[4] = 4 将p[4]返回
退到上一层
find(3) p[3] = 4 p[3] = 4 将p[3]返回
退到上一层
find(2) p[2] = 3 p[2] = 4 将p[2]返回
退到上一层
find(1) p[1] = 2 p[1] = 4 将p[1]返回
至此，我们发现所有的1，2，3的父节点全部置为了4，实现路径压缩；同时也实现了1的父节点的返回
nice!!

合并操作

合并就是让x的父节点的指针指向y
p[find(a)] = find(b); //将a的祖先点的父节点置为b的祖先节点

合并1， 5
find(1) = 3 find(5) = 4
p[find(1)] = find(5) –> p[3] = 4

其他路径压缩方法

1 路径分裂：使路径上的每个节点都指向其祖父节点（parent的parent）

int find(int x){
    while(x != p[x]){
        int parent = p[x];
        p[x] = p[p[x]];
        x = parent;
    }
    return x;
}
1
2
3
4
5
6
7
8

2 路径减半：使路径上每隔一个节点就指向其祖父节点（parent的parent）

int find(int x){
    while(x != p[x]){
        p[x] = p[p[x]];
        x = p[x];
    }
    return x;
}
1
2
3
4
5
6
7

全部代码

import java.util.*;
public class Main{
    static int N = 100010;
    static int[] p = new int[N];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
         //将n个数每个数各自都在一个集合里面。都指向自己，说明现在有多少个集合
        for(int i = 0 ; i < n ; i++){
            p[i]=i;
        }
        while(m-- > 0 ){
            String s = scan.next();
            int a = scan.nextInt();
            int b = scan.nextInt();
            if(s.equals("M")) p[find(a)] = find(b);//将a集合的根节点即祖先指向b集合的祖先 
            else{
                if(find(a) == find(b)) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
    //并查集的核心操作，寻找根节点祖先 + 路径压缩
    public static int find(int x){
        // 如果这个集合的父节点指向的不是自己，说明不是根节点，递归寻找，
        //最后找到根节点之后，把路径上的所有集合都指向根节点、
        if(p[x] != x) p[x] = find(p[x]); 
        return p[x]; // 最后返回根节点
    }
}

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