Kích thước thành phần lớn nhất theo ước chung trong C++

Cho mảng A các số nguyên dương duy nhất. Xây dựng đồ thị: đỉnh là các phần tử, có cạnh giữa A[i] và A[j] nếu chúng có ước chung > 1. Tìm kích thước thành phần liên thông lớn nhất.

Ví dụ: [4,6,15,35] → 4 (tất cả liên thông qua các ước chung).

Giải thuật

1. Dùng Union-Find (DSU) để gom nhóm các số có ước chung.
2. Với mỗi số x, phân tích thừa số nguyên tố. Với mỗi ước j (và x/j), union chỉ số hiện tại với chỉ số đầu tiên gặp ước đó (lưu trong map m).
3. Cuối cùng, tìm size lớn nhất của các nhóm (rank của root).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> parent, rank;
    int getParent(int x){
        if (parent[x] == -1) return x;
        return parent[x] = getParent(parent[x]);
    }
    void unionn(int x, int y){
        int parX = getParent(x), parY = getParent(y);
        if (parX == parY) return;
        if (rank[parX] >= rank[parY]) {
            rank[parX] += rank[parY];
            parent[parY] = parX;
        } else {
            rank[parY] += rank[parX];
            parent[parX] = parY;
        }
    }
    int largestComponentSize(vector<int>& A) {
        int ret = 0, n = A.size();
        parent = vector<int>(n, -1);
        rank = vector<int>(n, 1);
        unordered_map<int, int> m;
        for (int i = 0; i < n; i++) {
            int x = A[i];
            for (int j = 2; j * j <= x; j++) {
                if (x % j == 0) {
                    if (m.count(j)) unionn(m[j], i); else m[j] = i;
                    if (m.count(x/j)) unionn(m[x/j], i); else m[x/j] = i;
                }
            }
            if (m.count(x)) unionn(m[x], i); else m[x] = i;
            ret = max(ret, rank[getParent(i)]);
        }
        return ret;
    }
};
int main(){
    Solution ob;
    vector<int> v = {4,6,15,35};
    cout << (ob.largestComponentSize(v));
}

Đầu vào

{4,6,15,35}

Đầu ra

4