思路

初始化
void init() {
    for (int i=1; i<=n; i++) {
        fa[i] = i;
        size[i] = 1;
    }
}
找祖源
int find(int x) {
    if(fa[x]==x) return x;
    else return fa[x] = find(fa[x]);
}
合并连通块
void merge(int a,int b) {
    int x = find(a);
    int y = find(b);
    fa[x] = y;
    size[y] += size[x];
}
询问是否连通
bool ask(int a,int b) {
    return find(a)==find(b);
}

并查集算法思路及代码解析

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回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;

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


(2)维护size的并查集：

    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);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

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

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

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

C++ 代码

#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
using namespace std;
const int N = 1e5+5;
int n,m,a,b,fa[N], size[N];
string act;

void init() {
    for (int i=1; i<=n; i++) {
        fa[i] = i;
        size[i] = 1;
    }
}

int find(int x) {
    if(fa[x]==x) return x;
    else return fa[x] = find(fa[x]);
}

void merge(int a,int b) {
    int x = find(a);
    int y = find(b);
    fa[x] = y;
    size[y] += size[x];
}

bool ask(int a,int b) {
    return find(a)==find(b);
}

int main() {
    read(n),read(m);
    init();
    while(m--) {
        cin>>act;
        if(act=="C") {
            read(a),read(b);
            if(!ask(a,b)) merge(a,b);
        } else if(act=="Q1") {
            read(a),read(b);
            ask(a,b) ? printf("Yes\n") : printf("No\n");
        } else {
            read(a);
            printf("%d\n",size[find(a)]);
        }
    }   
    return 0;
}