C++

$\color{#cc33ff}{— > 算法基础课题解}$

思路：

并查集

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

$code1:$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], size1[N];

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

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) p[i] = i, size1[i] = 1;

    while (m --) {
        string op; 
        int a, b;
        cin >> op;

        if (op == "C") {
            cin >> a >> b;
            if (find(a) == find(b)) continue;
            size1[find(b)] += size1[find(a)];
            p[find(a)] = find(b);
        } else if (op == "Q1") {
            cin >> a >> b;
            puts(find(a) == find(b) ? "Yes" : "No");
        } else {
            cin >> a;
            cout << size1[find(a)] << endl;
        }
    }

    return 0;
}

$code2:$

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], size1[N];//p存储每个节点的父节点是谁,size1：每一个集合的大小（只有根节点的有意义）


//最基本的并查集
int find (int x){//返回x所在集合的编号（或者说：返回x的祖宗节点）+ 路径压缩
    if (p[x] != x) p[x] = find(p[x]);//如果p[x] != x,说明x不是根节点
    return p[x];
}

int main(){
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        p[i] = i;//将每个节点的父值赋成自己
        size1[i] = 1; //起始时每个集合只有一个点
    }

    while (m --){
        string op;
        int a, b;
        cin >> op;

        if (op == "C") {
            cin >> a >> b;
            if (find(a) == find(b)) continue;//如果a和b已经在一个集合里了，直接continue就可以啦
            size1[find(b)] += size1[find(a)];
            p[find(a)] = find(b); //pa的父节点直接等于pb
        }
        else if (op == "Q1"){
            cin >> a >> b;
            if (find(a) == find(b)) cout <<"Yes" << endl;//如果两个节点的祖宗节点相等，说明在一个集合里
            else cout << "No" << endl;
        }
        else {
            cin >> a;
            cout << size1[find(a)] << endl;
        }
    }
    return 0;
}