侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-11-10 / 0 评论 / 0 点赞 / 327 阅读 / 733 字
温馨提示:
本文最后更新于 2022-11-10,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

836. 合并集合


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

现在要进行 mm 个操作,操作共有两种:

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

输入格式

第一行输入整数 nnmm

接下来 mm 行,每行包含一个操作指令,指令为 M a bQ a b 中的一种。

输出格式

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

每个结果占一行。

数据范围

1n,m1051 \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 所在集合中去):(rpp 的集合编号,rqq 的集合编号) 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");
        }
    }
}
0

评论区