AcWing 837. 连通块中点的数量 - python3
原题链接
简单
作者:
KK_9
,
2022-11-30 22:36:16
,
所有人可见
,
阅读 163
class UnionFind:
def __init__(self, n):
self.parent = [None] * (1 + n)
self.count = {}
for i in range(1, 1 + n):
self.parent[i] = i
for i in range(1, 1 + n):
self.count[i] = 1
def find(self, a):
if self.parent[a] != a:
self.parent[a] = self.find(self.parent[a])
return self.parent[a]
def union(self, a, b):
if a == b: return
parentOfA = self.find(a)
parentOfB = self.find(b)
if parentOfA == parentOfB: return
self.parent[parentOfA] = parentOfB
self.count[parentOfB] += self.count[parentOfA]
def getNumberOfSet(self, a):
return self.count[self.find(a)]
def isConntected(self, a, b):
if a == b: return 'Yes'
if self.find(a) == self.find(b):
return 'Yes'
else:
return 'No'
n,m = map(int,input().split())
unionFind = UnionFind(n)
for i in range(m):
ops = input().split()
if ops[0] == 'C':
unionFind.union(int(ops[1]),int(ops[2]))
elif ops[0] == 'Q1':
print(unionFind.isConntected(int(ops[1]),int(ops[2])))
else:
print(unionFind.getNumberOfSet(int(ops[1])))