并查集练习_森林中的鸟
作者:
成理第一深情
,
2024-04-30 20:56:27
,
所有人可见
,
阅读 8
"""
思路:
1、同一张照片中的鸟:合并为同一个集合
2、判断一对鸟是否在一颗树上,即判断两个点是否在一个集合当中
3、树木的数量:集合的数量
4、鸟的数量:用set来存即可
时间复杂度分析:合并集合的时间复杂度为O(N *K * K)
"""
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
def find(x):
if x != p[x]:
p[x] = find(p[x])
return p[x]
n = int(input())
p = [i for i in range(11000)]
sz = set() # 用来统计所有出现过的鸟的编号,也就是鸟的数量
for _ in range(n):
opt = list(map(int, input().strip().split()))
k = opt[0]
for i in range(1, k + 1):
sz.add(opt[i]) # 不能把这段话加到下面这个for里,如果k为1,下面的for不会执行,那么会少数一只鸟
for j in range(i + 1, k + 1):
a = opt[i]
b = opt[j]
p[find(a)] = find(b) # 合并两个集合
res = 0
# print(sz)
for x in sz:
if p[x] == x:
res += 1
print(res, len(sz)) # 输出鸟的数量
Q = int(input())
while Q:
Q -= 1
a, b = map(int, input().strip().split())
if find(a) == find(b):
print("Yes")
else:
print("No")