题目描述

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

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

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

输入格式

第一行输入整数 $n$ 和 $m$。

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

输出格式

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

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

每个结果占一行。

数据范围

$1 \le n,m \le 10^5$

解法：采用按秩合并+路径压缩

并查集采用双亲表示法的树来存储，根结点的绝对值保存集合树中的成员数量。初始状态，各个根节点的值为-1，表示该集合中只有一个1个结点。如图所示：

按秩合并的思路：当进行合并操作时，需比较两个并查集的大小，再进行合并，保证小树合并到大树。当然也可以按照树的高度进行合并。

C++代码

#include <iostream>
using namespace std;

const int N = 100010;
int p[N];
int n, m;

void Union(int root1, int root2)
{
    if(root1 == root2) return;
    if(p[root2] > p[root1])
    {
        p[root1] += p[root2];
        p[root2] = root1;
    }
    else
    {
        p[root2] += p[root1];
        p[root1] = root2;
    }
}

int Find(int x)
{
    if(p[x] < 0)    return x;
    if(p[x] > 0)    p[x] = Find(p[x]);
    return p[x];
}

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

    for(int i = 1; i <= n; i ++)
        p[i] = -1;

    while(m --)
    {
        string op;
        cin >> op;
        int a, b;
        if(op[0] == 'C')
        {
            cin >> a >> b;
            Union(Find(a), Find(b));
        }
        else if(op[1] == '1')
        {
            cin >> a >> b;
            if(Find(a) == Find(b))          puts("Yes");
            else                            puts("No");
        }
        else
        {
            cin >> a;
            cout << -p[Find(a)] << endl;
        }
    }

    return 0;
}