算法008-并查集

并查集

并查集就是将大规模的集合中，将有关联的组合在一起。最后将某一组由一个根来替代。整体分为，查和合。

代码

class UFind {
    vector<int> parent; //表示i所在组的根
    vector<int> rank; // 表示以i为根时，他的深度，用于方便将短根接到长根，减少find深度
public:
    UFind(int n) {
        parent = vector<int>(n);
        rank = vector<int>(n);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) { // 查找对应值所在的根
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 优化：直接指向根，而不需要每次指上个点
        }
        return parent[x];
    }

    void uni(int x, int y) { // 将两个点或者两个不同的组合成一个组
        int a = find(x);
        int b = find(y);
        if (a != b) {
            if (rank[a] > rank[b]) { // 短根接长根
                parent[b] = a;
            } else if (rank[b] > rank[a]) {
                parent[a] = b;
            } else { // 相同就随便接，但被接的长度肯定要+1
                parent[b] = a;
                rank[a]++;
            }
        }
    }
};

按公因数计算最大组件大小

给定一个由不同正整数的组成的非空数组 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

示例 3：

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

提示：
1 <= nums.length <= 2 * 104 > 1 <= nums[i] <= 105 > nums 中所有值都不同

思路

选用并查集，将公因数相同的并为一组，比如:[2, 6, 9] 虽然2和9不能直接并为一组，但是2可以和6，6可以和9并为一组，所以2和9间接并为一组。

代码

// 并查集略
class Solution {
public:
    int largestComponentSize(vector<int> nums) {
        int MAXN = *max_element(nums.begin(), nums.end());
        UFind uf(MAXN + 1);
        for (int num : nums) {
            for (int i = 2; i * i <= num; i++) { // 这里虽然将所有相关的公因数都并到一组，但实际只关系nums数组的有没并为一组
                if (num % i == 0) {
                    uf.uni(num, i);
                    uf.uni(num, num / i);
                }
            }
        }

        vector<int> counts(MAXN + 1);
        for (int num : nums) {
            int root = uf.find(num);
            counts[root]++;
        }

        return  *max_element(counts.begin(), counts.end());
    }
};