837. 连通块中点的数量
摘要
Title: 837. 连通块中点的数量
Tag: 并查集
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
837. 连通块中点的数量
-
题意
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
Q2 a，询问点 a 所在连通块中点的数量； -
思路
新建一个size数组，表示集合中点的数量
注意：- 只有根节点的size值是有意义的
- 当两个根合并时，若a连向b，则b的大小加上a的大小
- 当a和b在同一个集合时，不进行size相关操作
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37'''
Author: NEFU AB-IN
Date: 2022-03-01 18:40:18
FilePath: \ACM\Acwing\837.py
LastEditTime: 2022-03-01 19:09:25
'''
N = int(1e5 + 10)
fa = [_ for _ in range(N)]
size = [1 for _ in range(N)] #全部初始化1
def find(x):
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
n, m = map(int, input().split())
for i in range(m):
lst = input().split()
if lst[0] == 'C':
a, b = int(lst[1]), int(lst[2])
if find(a) == find(b): # 需continue
continue
size[find(b)] += size[find(a)]
fa[find(a)] = find(b)
elif lst[0] == 'Q1':
a, b = int(lst[1]), int(lst[2])
if find(a) == find(b):
print("Yes")
else:
print("No")
else:
a = int(lst[1])
print(size[find(a)])