题目描述

给定初始n个点无边的无向图，支持下面三种操作：
1. C a b 此操作将a b 连起来，a和b可能相等也可能已经连接过；
2. Q1 a b 此操作查询a与b是否处在同一个连通块中(有路径连通)；
3. Q2 a 查询a所在连通块中有多少个元素；

算法1

并查集

• 这题首先无向图只判断是否连通(处于同一连通块)，所以图内部边是怎样连起来的其实不重要，表面上是图的题其实是集合的题，于是可以用并查集来做；
• 此题相较于上一题仅增加一个查询当前块有多少元素的操作，增加一个属性数组记录一下即可；

C++ 代码

#include<iostream>
using  namespace std;

const int N = 1e5+10;
int p[N], c[N];                     //p[]为并查集数组，c[]为记录每个集合有多少个元素；

void init(int n){                   //初始并查集数组中每个节点的集合为自己，且每个节点只有一个元素
    for(int i = 1; i <= n; ++i){
        p[i] = i;
        c[i] = 1;
    }
}

int find(int x){                    //经典寻找祖先节点以及路径压缩；
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a != b){                     //仅当a,b不在一个集合时才有如下操作；
        p[a] = p[b];                //令a所在集合并入b所在集中；
        c[b] += c[a];               //b所在集合节点数要加上a所在集合节点数；
    }
}

void query1(int a, int b){
    cout<<(find(a) == find(b) ? "Yes" : "No")<<endl;
}

void query2(int a){
    cout<<c[find(a)]<<endl;
}

int main()
{
    int n, m;
    cin>>n>>m;
    init(n);
    string op;
    int a, b;
    while(m--){
        cin>>op;
        if(op == "C"){
            cin>>a>>b;
            merge(a, b);
        }
        else if(op == "Q1"){
            cin>>a>>b;
            query1(a, b);
        }
        else{
            cin>>a;
            query2(a);
        }
    }
    return 0;
}