Skip to content

952. Largest Component Size by Common Factor

952. Largest Component Size by Common Factor

题目: https://leetcode.com/problems/largest-component-size-by-common-factor/

难度: Hard

题意：

  1. 给n个数
  2. 将n个数设定为n个节点，如果两个数之间的最大公约数大于1，则连边
  3. 求图的最大联通分量的大小

思路：

  • n的数据量高达2w，如果两两节点计算最大公约数，复杂度是o(n^2logn)
  • 我们可以使用素数筛法来取出需要两两画线的数列，比如：取出被2整除的数，被3整除的数。。。
  • 求图的最大联通分量可以用并查集来做
  • 过程是这样的
  • 枚举所有的素数
  • 假设当前枚举的素数是i
  • 从n个数中取出所有能被i整除的数
  • 假设有m个数，那么第1个数跟第m-1个数都跟第0个数做下合并
  • 枚举结束后，求最大的集合的大小
  • 素数筛法的复杂度是o(nlogn)，这里需要做下优化，如果枚举每个素数都得从n个数寻找能被它整除的数，复杂度还是o(nk)，k是素数的个数，但如果我们把n个数映射到1-100000的数组中，就可以套用素数筛法了

解法：

bool isPrime[100100];
bool hasValue[100100];
int p[100100];
int size[100100];
class Solution {
public:
    bool inited = false;

    void init() {
        memset(isPrime, true, sizeof(isPrime));
        for (int i = 2;i <= 100000;i++) {
            if (!isPrime[i]) {
                continue;
            }
            for (int j = i + i;j <= 100000;j += i) {
                isPrime[j] = false;
            }
        }
    }

    int find_set(int x) {
        vector<int> temp;
        while (p[x] != x) {
            temp.push_back(x);
            x = p[x];
        }
        for (int i = 0;i < temp.size();i++) {
            p[temp[i]] = x;
        }
        return x;
    }

    void union_set(int x, int y) {
        x = find_set(x);
        y = find_set(y);
        if (x == y) {
            return;
        }
        p[x] = y;
        size[y] += size[x];
    }

    vector<int> find(int prime) {
        vector<int> ret;
        for (int i = prime;i <= 100000;i += prime) {
            if (hasValue[i]) {
                ret.push_back(i);
            }
        }
        return ret;
    }

    int largestComponentSize(vector<int>& A) {
        if (!inited) {
            init();
            inited = true;
        }

        memset(hasValue, false, sizeof(hasValue));
        for (int i = 0;i < A.size();i++) {
            hasValue[A[i]] = true;
        }
        for (int i = 0;i <= 100000;i++) {
            p[i] = i;
            size[i] = 1;
        }
        for (int i = 2;i <= 100000;i++) {
            if(isPrime[i]) {
                vector<int> temp = find(i);

                if (temp.size() == 0){
                    continue;
                }

                for (int j = 1;j < temp.size();j++) {
                    union_set(temp[0], temp[j]);
                }
            }
        }

        int ret = 0;
        for (int i = 0;i <= 100000;i++) {
            if (!hasValue[i]) {
                continue;
            }
            int x = find_set(i);
            if (size[x] > ret) {
                ret = size[x];
            }
        }
        return ret;
    }
};
回到顶部