class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def areConnected(
self, n: int, threshold: int, queries: List[List[int]]
) -> List[bool]:
uf = UnionFind(n + 1)
for a in range(threshold + 1, n + 1):
for b in range(a + a, n + 1, a):
uf.union(a, b)
return [uf.find(a) == uf.find(b) for a, b in queries]