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

题目

837. 连通块中点的数量

---

给定一个包含 $n$ 个点（编号为 $1 \sim n$）的无向图，初始时图中没有边。

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

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

输入格式

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

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

输出格式

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

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

每个结果占一行。

数据范围

$1 \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)]);
            }
        }
    }
}