Leetcode 3378. Count Connected Components in LCM Graph

• Leetcode 3378. Count Connected Components in LCM Graph
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3378. Count Connected Components in LCM Graph

1. 解题思路

这一题整体思路上是一个很典型的cluster聚合问题，因此我们使用DSU的方法很容易就能够考察最终整个图有多少个独立子图。关于DSU的算法，网上有很多，我自己也整理了一个小文章作为备忘（经典算法：并查集（DSU）结构简介），因此这里我们就不过多展开了，有兴趣的读者可以移步先去了解一下。

下面，我们就只需要考察如何对算法进行优化即可，因为如果暴力地考察任意两个数之间的lcm，那算法复杂度将会是$O(N^2)$，显然过大了。因此，我们需要对这部分内容进行优化。

这里，我的优化思路是仿照素数遍历的思路。我们首先将所有的数字有序排列，然后从小到大依次找到当前数组当中的“质数”，即对应的数在当前数组当中必然无法找到另一个数将其整除。至于剩下所有的数，其必然为这些“质数”的倍数，我们直接将其与对应的“质数”聚合即可。

然后，有了这些“质数”之后，事实上我们就已经获得了一个个子图的核元素，然后，我们只需要两两考察这些元素之间是否lcm小于给定的阈值threshold，然后我们就可以将其进行最终的聚合，此时我们就能够得到最终的子图之间的相互连接关系了。

2. 代码实现

给出python代码实现如下：

class DSU:
    def __init__(self, N):
        self.root = [i for i in range(N)]
        self.cluster_num = N
        
    def find(self, k):
        if self.root[k] != k:
            self.root[k] = self.find(self.root[k])
        return self.root[k]
    
    def union(self, a, b):
        x = self.find(a)
        y = self.find(b)
        if x != y:
            self.root[y] = x
            self.cluster_num -= 1
        return


class Solution:
    def countComponents(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        dsu = DSU(n)
        nums = sorted(nums)
        index = {x: i for i, x in enumerate(nums)}
        status = [0 for _ in range(threshold+1)]
        cores = []
        for i, x in enumerate(nums):
            if x > threshold:
                break
            if status[x] == 1:
                continue
            for c in cores:
                if math.lcm(c, x) <= threshold:
                    dsu.union(index[c], i)
            cores.append(x)
            for j in range(x, threshold+1, x):
                status[j] = 1
                if j in index:
                    dsu.union(i, index[j])
        return dsu.cluster_num

提交代码评测得到：耗时1126ms，占用内存42.4MB。