并查集

Trace

连通块中点的数量

传送门：https://www.acwing.com/problem/content/839/

Problem

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

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

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

输入格式

第一行输入整数 nn 和 mm。

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

输出格式

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

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

每个结果占一行。

数据范围

1≤n,m≤1e5

输入样例：

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

输出样例：

Yes
2
3

思路：

并查集基础模板题

$cnt[N]$：记录每个集合中元素个数

$p[N]$：存当前节点父结点，路径压缩后存根结点

合并集合时先合并数量，再连边。

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;

// p[i]：节点i的根节点
// p[i]=i，i为根节点
int p[N];
// 记录每个集合中的元素个数
int cnt[N];

int n,m;

// 寻找x的根节点
int find(int x){
    // 如果x不是根节点
    if(x!=p[x]) 
        // 将p[x]设置为根节点
        p[x]=find(p[x]);
    // 返回根节点
    return p[x];
}

int main()
{
    cin>>n>>m;
    // 初始化
    for(int i=1;i<=n;i++){
        // 每个点都是根节点，各自为一个集合
        p[i]=i;
        // 每个集合一开始只有1个点（自己）
        cnt[i]=1;
    }
    while(m--){
        string s;
        cin>>s;
        int x,y;
        if(s=="Q2"){
            cin>>x;
            cout<<cnt[find(x)]<<endl;
        }
        else if(s=="Q1"){
            cin>>x>>y;
            if(find(x)==find(y)){
                cout<<"Yes"<<endl;
            }
            else{
                cout<<"No"<<endl;
            }
        }
        else{
            cin>>x>>y;
            
            // x与y不能再同一个集合
            if(find(x)!=find(y)){
                // 先更新cnt
                cnt[find(y)]+=cnt[find(x)];
                // 将根节点连起来
                p[find(x)]=find(y);
            }
            
        }
    }
}

$find()$时间复杂度可以看成$O(1)$。