关于#优化算法#的问题，如何解决？

Question

问题遇到的现象和发生背景

leetcode每日一题，给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：
有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。
返回 图中最大连通组件的大小 。
示例 1：
输入：nums = [4,6,15,35]
输出：4
示例 2：
输入：nums = [20,50,9,63]
输出：2

问题相关代码，请勿粘贴截图

def find(list,nums):
        for m in list:
            for k in nums:
                if k not in list and math.gcd(k, m) > 1:
                    list.append(k)
class Solution:
    
    def largestComponentSize(self, nums: List[int]) -> int:
        list1=[]
        for i in nums:
            list=[i]
            for j in nums:
                if i!=j and math.gcd(i,j)>1:
                    list.append(j)
            while True:
                a=len(list)
                find(list,nums)
                b=len(list)
                if a==b:
                    break
            list1.append(len(list))
        return max(list1)

运行结果及报错内容

循环语句太多导致遇到非常长的数字就超出时间限制了。

我想要达到的结果

算法本身能算出正确得数。
请评价一下我的算法，有没有优化空间。

Answer 1

时间复杂度为O(n4),一般超过O(n3)算法上就存在问题。
参考：

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def merge(self, x: int, y: int) -> None:
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
        elif self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += 1

class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        uf = UnionFind(max(nums) + 1)
        for num in nums:
            i = 2
            while i * i <= num:
                if num % i == 0:
                    uf.merge(num, i)
                    uf.merge(num, num // i)
                i += 1
        return max(Counter(uf.find(num) for num in nums).values())