LC 1627. 带阈值的图连通性

https://leetcode-cn.com/problems/graph-connectivity-with-threshold/

之前没有遇到过这种需要计算多重连通性的问题，所以有点卡壳了。可以想象，这题使用使用 `gcd` 不断地去尝试所有连接点，然后再使用类似BFS/DFS来查找连通性，时间复杂度会很高。

有效解决多重连通性的一个思路就是使用Find/Union数据结构。可以想象，如果a<->b, b<->c的话，那么也说a<->c，而这个知识在Find/Union的时候就自动计算出来了。

具体到这道题目上，我们可以遍历所有 `pair(a,b) st. gcd(a, b>threshold` 。如果a<-b>, b<->c的话，那么在查询Find/Union数据结构的时候, a<->c这个关联就会存在了。

class Solution:
    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:
        P = [-1] * (n + 1)

        def union(x, y):
            px = parent(x)
            py = parent(y)
            if px == py: return
            P[px] = py

        def parent(x):
            p = x
            while P[p] != -1:
                p = P[p]

            while x != p:
                x2 = P[x]
                P[x] = p
                x = x2
            return p

        ans = []
        if threshold == 0:
            ans.extend([True] * len(queries))
            return ans

        for x in range(threshold + 1, n + 1):
            for y in range(2, n // x + 1):
                union(x, x * y)

        for x, y in queries:
            px = parent(x)
            py = parent(y)
            ans.append(px == py)
        return ans