侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【并查集】连通块中点的数量

GabrielxD
2022-11-10 / 0 评论 / 0 点赞 / 27 阅读 / 738 字 / 正在检测是否收录...

题目

837. 连通块中点的数量


给定一个包含 nn 个点(编号为 1n1 \sim n)的无向图,初始时图中没有边。

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

  1. C a b,在点 aa 和点 bb 之间连一条边,aabb 可能相等;
  2. Q1 a b,询问点 aa 和点 bb 是否在同一个连通块中,aabb 可能相等;
  3. Q2 a,询问点 aa 所在连通块中点的数量;

输入格式

第一行输入整数 nnmm

接下来 mm 行,每行包含一个操作指令,指令为 C a bQ1 a bQ2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b,如果 aabb 在同一个连通块中,则输出 Yes,否则输出 No

对于每个询问指令 Q2 a,输出一个整数表示点 aa 所在连通块中点的数量

每个结果占一行。

数据范围

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

输入样例:

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例:

Yes
2
3

解题

方法一:并查集

思路

并查集模板题:并查集 - 维护每个集合大小的并查集

注意:若两节点本身已在同一集合内的话就不需要再做一次合并了。

代码

#include <iostream>
#include <cstring>

using namespace std;

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

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

void join(int p, int q) {
    int rp = find(p), rq = find(q);
    if (rp != rq) {
        roots[rp] = rq;
        sizes[rq] += sizes[rp];
    }
}

int main() {
    scanf("%d%d\n", &n, &m);
    for (int i = 1; i <= n; ++i) roots[i] = i, sizes[i] = 1;
    while (m--) {
        char ope[2];
        int a, b;
        scanf("%s", ope);
        if (!strcmp(ope, "C")) {
            scanf("%d%d\n", &a, &b);
            join(a, b);
        } else if (!strcmp(ope, "Q1")) {
            scanf("%d%d\n", &a, &b);
            printf(find(a) == find(b) ? "Yes\n" : "No\n");
        } else {
            scanf("%d", &a);
            printf("%d\n", sizes[find(a)]);
        }
    }
    
    return 0;
}
import java.util.*;
import java.io.*;

public class Main {
    static int[] roots, sizes;
    
    static int find(int x) {
        return x == roots[x] ? x : (roots[x] = find(roots[x]));
    }
    
    static void union(int p, int q) {
        int rp = find(p), rq = find(q);
        if (rp != rq) {
            roots[rp] = rq;
            sizes[rq] += sizes[rp];
        }
    }
    
    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];
        sizes = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            roots[i] = i;
            sizes[i] = 1;
        }
        while (m-- > 0) {
            in.nextToken();
            String ope = in.sval;
            if (ope.equals("C")) {
                in.nextToken();
                int a = (int) in.nval;
                in.nextToken();
                int b = (int) in.nval;
                if (a != b) union(a, b);
            } else if (ope.equals("Q1")) {
                in.nextToken();
                int a = (int) in.nval;
                in.nextToken();
                int b = (int) in.nval;
                System.out.println(find(a) == find(b) ? "Yes" : "No");
            } else {
                in.nextToken();
                int a = (int) in.nval;
                System.out.println(sizes[find(a)]);
            }
        }
    }
}

0

评论区