C++-এ কমন ফ্যাক্টর দিয়ে সর্বোচ্চ কম্পোনেন্ট সাইজ

সমস্যা বিবরণ

ইউনিক পূর্ণসংখ্যা অ্যারে A দেওয়া থাকলে, একটি গ্রাফ তৈরি করা হয় যেখানে নোডগুলো A[i]। দুটি নোডের মধ্যে এজ থাকবে যদি তাদের কমন ফ্যাক্টর ১ থেকে বড় হয়। সর্বোচ্চ কানেক্টেড কম্পোনেন্টের সাইজ বের করতে হবে।

উদাহরণ

A = [4,6,15,35] → আউটপুট = 4 (সব নোড একই কম্পোনেন্টে)

সমাধান পদ্ধতি

• ইউনিয়ন-ফাইন্ড (DSU) ডেটা স্ট্রাকচার ব্যবহার করা হয়।
• প্রতিটি সংখ্যার প্রাইম ফ্যাক্টর বের করে, সেই ফ্যাক্টর দিয়ে ইউনিয়ন করা হয়।
• র‍্যাঙ্ক বেসড ইউনিয়ন ও পাথ কম্প্রেশন ব্যবহার করা হয়।
• সর্বোচ্চ র‍্যাঙ্ক মানই উত্তর।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

class Solution {
    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;
        }
    }
    
public:
    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);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {4,6,15,35}

আউটপুট: 4