XiYuJing|文章:连通块中点的数量

[[ slide_text ]]

[[item.c]]

连通块中点的数量

发布时间：2022年10月09日 作者：靖华来源：XiYuJing

算法 C++ 并查集

# 连通块中点的数量
给定一个包含 n 个点（编号为 1∼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≤n,m≤10<sup>5</sup>

#### 输入样例：

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

#### 输出样例：

```
Yes
2
3
```
> 题目来源于AcWing

### 代码
```
#include<iostream>
using namespace std;
const int N = 1e5+10;
int p[N],n,m,num[N];
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);// 如果他不是根就找他指向的根
    return p[x];
}
int main()
{

string s;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        num[i]=1;
    }
    while(m--)
    {
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;
            a = find(a),b = find(b);
            if(a!=b)
            {
                p[a]=b;
                num[b]+=num[a];
            }
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b))puts("Yes");
            else puts("No");
        }
        else 
        {
            cin>>a;
            cout<<num[find(a)]<<endl;
        }
    }
}
```

你觉得文章怎么样

已浏览 113 次，0 条评论