$$\color{Red}{连通块中点的数量 简单通透 三种语言}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

合并集合简单通透三种语言

唯一和合并集合不同的就是需要增加一个数组存储当前这个祖先节点内部的集合数量
这道题唯一的难点在于要意识到当两个集合不在同一个连通块的情况下，我们才要把数量相加，如果已经在了，就肯定是已经合并的了，不能多加一次数量

java

import java.io.*;

public class Main {
    static int N = 100010, n, m;
    static int[] p = new int[N];
    static int[] cnt = new int[N];

    static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            p[i] = i;
            cnt[i] = 1;
        }
        for (int i = 0; i < m; i++) {
            String[] op = br.readLine().split(" ");
            if ("Q2".equals(op[0])) {
                int a = Integer.parseInt(op[1]);
                a = find(a);
                System.out.println(cnt[a]);
            } else if("C".equals(op[0])) {
                int a = Integer.parseInt(op[1]);
                int b = Integer.parseInt(op[2]);
                a = find(a);
                b = find(b);
                if (a != b) {
                    cnt[b] += cnt[a];
                    p[a] = b;
                }
            }else{
                int a = Integer.parseInt(op[1]);
                int b = Integer.parseInt(op[2]);
                if(find(a) != find(b)) System.out.println("No");
                else System.out.println("Yes");
            }
        }
    }
}

python3 代码

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

n, m =  map(int, input().split())
p = [int(x) for x in range(n+10)]
cnt = [1 for i in range(n+10)]

for i in range(m):
    op = input().split()

    if op[0] == 'C':
        a, b = int(op[1]), int(op[2])
        a, b = find(a), find(b)
        if a != b:
            cnt[b] += cnt[a]
            p[a] = b

    elif op[0] == 'Q1':
        a, b = int(op[1]), int(op[2])
        a, b = find(a), find(b)   
        if a != b:
            print('No')
        else:
            print('Yes')

    elif op[0] == 'Q2':
        x = int(op[1])
        x = find(x)
        print(cnt[x])

C++ 代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int p[N], s[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m, a, b;
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        p[i] = i;
        s[i] = 1;
    }
    while(m--)
    {
        string op;
        cin >> op;
        if(op == "C")
        {
            scanf("%d%d", &a, &b);
            if(find(a) != find(b))
            {
                s[find(b)] += s[find(a)];
                p[find(a)] = find(b);
            }
        }
        else if(op == "Q1")
        {
            scanf("%d%d", &a, &b);
            if(find(a) == find(b))  printf("Yes\n");
            else                    printf("No\n");
        }
        else  
        {
            scanf("%d", &a);
            printf("%d\n", s[find(a)]);
        }
    }
    return 0;
}