leetcode：952. 按公因数计算最大组件大小【并查集】

分析

一个数，它和它所有的因数都应该是一组
然后对所有数都这样分解
最后，对所有数，可以得到root
这个root就是对应的分组

ac code

class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        n = len(nums)



        parent = list(range(10 ** 5 + 10))
        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1: int, index2: int):
            # 后者作为爸爸
            parent[find(index1)] = find(index2)
        

        for num in nums:
            upper_bound = int(sqrt(num))
            # core code
            for i in range(2, upper_bound + 1):
                if num % i == 0:
                    union(num, i)
                    union(num, num // i)

        ans = 1
        cnt = [0] * (10 ** 5 + 10)
        for num in nums:
            root = find(num)
            cnt[root] += 1
            ans = max(ans, cnt[root])
        
        return ans

总结

简单并查集应用