AcWing 1608. 森林里的鸟
原题链接
简单
作者:
aac
,
2024-11-25 00:47:26
,
所有人可见
,
阅读 1
N = int(1e5 + 10)
p = [0] * N
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
for i in range(N):
p[i] = i
n = int(input())
cnt = 0 # 记录合并了多少次集合
se = set()
for i in range(n):
k,*birds = list(map(int,input().split()))
se.add(birds[0])
for i in range(1,k): # 对当前集合中的鸟进行两两合并操作
se.add(birds[i])
a = birds[i - 1];b = birds[i]
pa = find(a);pb = find(b)
if pa != pb:
p[pa] = pb
cnt += 1 # 合并集合次数加一
bird_num = len(se)
"""
并查集初始化时有bird_num个集合,合并了cnt次集合,
所以最终的集合数量为bird_num - cnt
"""
print(bird_num - cnt,bird_num)
q = int(input())
while q > 0:
q -= 1
a,b = map(int,input().split())
pa = find(a);pb = find(b)
if pa != pb:
print("No")
else:
print("Yes")