# 952.按公因数计算最大组件大小 (Hard)

## 问题描述
[952. 按公因数计算最大组件大小 (Hard)](https://leetcode.com/problems/largest-component-size-by-common-factor/)

给定一个由不同正整数的组成的非空数组 `nums` ，考虑下面的图：

- 有 `nums.length` 个节点，按从 `nums[0]` 到 `nums[nums.length - 1]`
标记；
- 只有当 `nums[i]` 和 `nums[j]` 共用一个大于 1 的公因数时， `nums[i]` 和
`nums[j]` 之间才有一条边。

返回 图中最大连通组件的大小 。

**示例 1：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065527.png)

```
输入：nums = [4,6,15,35]
输出：4

```

**示例 2：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065528.png)

```
输入：nums = [20,50,9,63]
输出：2

```

**示例 3：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-65531.png)

```
输入：nums = [2,3,6,7,4,12,21,39]
输出：8

```

**提示：**

- `1 <= nums.length <= 2 * 10⁴`
- `1 <= nums[i] <= 10⁵`
- `nums` 中所有值都 **不同**

## 解题思路
使用[并查集](https://blog.zwyyy456.tech/zh/posts/tech/dsu-oi-wiki/)，并注意[质因数分解](https://blog.zwyyy456.tech/zh/posts/tech/prime_factorization/)的求法。

由于`nums[i] <= 100000`，因此我们设置初始的并查集的节点为$100001$个，遍历数组中的每个元素，将每个元素和他的质因数连接起来，我们只将`size_[nums[i]]`初始化为1，其余均为0，这样不属于`nums[i]`的质因数的个数就不会被统计到树的数量中，遍历数组的元素时，更新`ans`即可。

注意，由于时间复杂度的要求，我们需要压缩路径并且使用启发式合并。

## 代码
```cpp
class Dsu {
public:
    vector<int> parent_;
    vector<int> size_; // 每棵树的节点数量
    int res;
public:
    Dsu(int n) : parent_(n), size_(n, 0), res(0) {
        iota(parent_.begin(), parent_.end(), 0); // parent[0] = 0, parent[1] = 1, 依次类推
    }
    int find(int idx) {
        return parent_[idx] == idx ? idx : parent_[idx] = find(parent_[idx]); 
    } 
    void unite(int idx, int idy) {
        idx = find(idx);
        idy = find(idy);
        if (idx == idy) {
            return;
        }
        if (size_[idx] < size_[idy]) {
            std::swap(idx, idy);
        }
        parent_[idy] = idx;
        size_[idx] += size_[idy];
    }

};
class Solution {
  public:
    void factor(int num, Dsu *dsu) {
        int tmp = num;
        for (int i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                while (num % i == 0) {
                    num /= i;
                }
                dsu->unite(i, tmp);
            }
        }
        if (num != 1) {
            dsu->unite(num, tmp);
        }
        dsu->res = std::max(dsu->res, dsu->size_[dsu->find(tmp)]);

    }
    int largestComponentSize(vector<int> &nums) {
        int n = nums.size();
        Dsu *dsu = new Dsu(100000 + 1);
        for (int i = 0; i < n; ++i) {
            dsu->size_[nums[i]] = 1;
        }
        for (int i = 0; i < n; ++i) {
            factor(nums[i], dsu);
        }
        return dsu->res;
    }
};
```