P3367 【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

样例输出 #1

1
2
3
4
N
Y
N
Y

提示

对于 $30%$ 的数据，$N \le 10$，$M \le 20$。

对于 $70%$ 的数据，$N \le 100$，$M \le 10^3$。

对于 $100%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$，$1 \le X_i, Y_i \le N$，$Z_i \in { 1, 2 }$。

题解

分析

  • 样例的图解

第一步
1 2 是否为同一个 集合？ F 指向自己返回 1 ，2同理 返回 2

image.png

则有返回false

image.png

image.png

第二步
x 的索引指向 y 的索引
1 指向 2

image.png

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    static int[] map;
    
    // 查找
    public static int find(int i) {
        if (i != map[i]) map[i] = find(map[i]);
        return map[i];
    }
    
    // 判断是否为同一个集合
    public static boolean isSameSet(int x, int y) {
        // 一样的爹
        return find(x) == find(y);
    }
    
    // 合并操作
    public static void union(int x, int y) {
        map[find(x)] = find(y);
    }

    public static void main(String[] args) throws IOException {
        while (st.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) st.nval;
            map = new int[n + 5];
            // 初始化
            for (int i = 0; i <= n; i++) map[i] = i;
            
            int m = nextInt();

            // 循环操作
            for (int i = 0; i < m; i++) {
                // 操作啥
                int z = nextInt();
                
                int x = nextInt();
                int y = nextInt();

                // 合并
                if (z == 1) {
                    union(x, y);
                } else {
                    boolean same = isSameSet(x, y);
                    System.out.println(same ? "Y" : "N");
                }
            }
        }

    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    static StreamTokenizer st = new StreamTokenizer(br);
    
    static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

}

视频讲解原理(cpp版本)

  • Disjoint Set 即 不相交集合

老师的生动讲解

8a8c168e5588e2dc0cfb7bf1eb791c5c.png

视频讲解(java)

左程云 并查集上