【并查集】合并集合「并查集基础」

题目

836. 合并集合

---

一共有 $n$ 个数，编号是 $1 \sim n$，最开始每个数各自在一个集合中。

现在要进行 $m$ 个操作，操作共有两种：

1. M a b，将编号为 $a$ 和 $b$ 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 $a$ 和 $b$ 的两个数是否在同一个集合中；

输入格式

第一行输入整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 $a$ 和 $b$ 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

$1 \le n,m \le 10^5$

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

解题

方法一：并查集

思路

并查集模板题：并查集 - 路径压缩优化的并查集

并查集

基本作用：

• 将两个集合合并。
• 询问两个元素是否在一个集合当中。

基本原理：每个集合用一棵树表示，树根的编号就是整个集合的编号。每个节点存储它的父节点（代码中 roots[x] 就表示 x 的父节点）。

一些操作：

• 判断树根：roots[x] == x。
• 求 x 的集合编号（迭代）：while (roots[x] != x) x = roots[x]。
• 合并两个集合（把 p 所在集合合并到 q 所在集合中去）：（rp 指 p 的集合编号，rq 指 q 的集合编号） roots[rp] = rq。

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int roots[N];
int n, m;

int find(int x) {
    return x == roots[x] ? x : (roots[x] = find(roots[x]));
}

void join(int p, int q) {
    roots[find(p)] = find(q);
}

int main() {
    scanf("%d%d\n", &n, &m);
    for (int i = 1; i <= n; ++i) roots[i] = i;
    while (m--) {
        char ope;
        int a, b;
        scanf("%c %d %d\n", &ope, &a, &b);
        if (ope == 'M') join(a, b);
        else printf(find(a) == find(b) ? "Yes\n" : "No\n");
    }
    
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int[] roots;
    
    static int find(int x) {
        return x == roots[x] ? x : (roots[x] = find(roots[x]));
    }
    
    static void union(int p, int q) {
        roots[find(p)] = find(q);
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        roots = new int[n + 1];
        for (int i = 1; i <= n; ++i) roots[i] = i;
        while (m-- > 0) {
            in.nextToken();
            char ope = in.sval.charAt(0);
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            if (ope == 'M') union(a, b);
            else System.out.println(find(a) == find(b) ? "Yes" : "No");
        }
    }
}