C++ এ কমন ফ্যাক্টর দ্বারা সবচেয়ে বড় উপাদানের আকার

ধরুন আমাদের কাছে অনন্য ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে রয়েছে, এখন নিম্নলিখিত গ্রাফটি বিবেচনা করুন −

একটি সংখ্যক নোডের দৈর্ঘ্য রয়েছে, এগুলিকে A[0] থেকে A[A - 1 এর আকার] লেবেল করা হয়েছে; A[i] এবং A[j] এর মধ্যে একটি প্রান্ত থাকে যখন A[i] এবং A[j] 1-এর চেয়ে বেশি একটি সাধারণ গুণনীয়ক ভাগ করে। আমাদের গ্রাফে সবচেয়ে বড় সংযুক্ত উপাদানটির আকার খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি [4,6,15,35] এর মত হয়, তাহলে আউটপুট হবে 4

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি অ্যারে অভিভাবক সংজ্ঞায়িত করুন

• একটি অ্যারে র‍্যাঙ্ক সংজ্ঞায়িত করুন

• একটি অ্যারে র‍্যাঙ্ক সংজ্ঞায়িত করুন

• যদি অভিভাবক[x] -1 এর মত হয়, তাহলে −

  • রিটার্ন x

• রিটার্ন প্যারেন্ট[x] =getParent(অভিভাবক[x])

• একটি ফাংশন unionn() সংজ্ঞায়িত করুন, এটি x, y,

  লাগবে

• parX :=getParent(x)

• parY :=getParent(y)

• যদি parX parY এর মত হয়, তাহলে −

  • ফেরত

• যদি rank[parX]>=rank[parY] হয়, তাহলে −

  • rank[parX] :=rank[parX] + rank[parY]

  • পিতামাতা[parY] :=parX

• অন্যথায়

  • rank[parY] :=rank[parY] + rank[parX]

  • অভিভাবক[parX] :=parY

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• ret :=0, n :=A

  এর আকার

• অভিভাবক :=আকারের একটি অ্যারে সংজ্ঞায়িত করুন n এটি -1 দিয়ে পূরণ করুন

• rank :=আকারের একটি অ্যারে সংজ্ঞায়িত করুন এবং এটি 1 দিয়ে পূরণ করুন

• একটি মানচিত্র m

  সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • x :=A[i]

  • আরম্ভ করার জন্য j :=2, যখন j * j <=x, আপডেট করুন (j 1 দ্বারা বাড়ান), −

    • যদি x mod j 0 এর মত হয়, তাহলে &minsu;

      • j যদি m হয়, তাহলে −

        • unionn(m[j], i)

      • অন্যথায়

        • m[j] :=i

      • যদি (x / j) m হয়, তাহলে −

        • unionn(m[x / j], i)

      • অন্যথায়

        • m[x / j] =i

  • যদি x m হয়, তাহলে −

    • unionn(m[x], i)

  • অন্যথায়

    • m[x] :=i

  • ret :=ret এবং র্যাঙ্কের সর্বাধিক [getParent(i)]

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<int> parent;
   vector<int> 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);
      int 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;
      int 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;
   }
};
main(){
   Solution ob;
   vector<int> v = {4,6,15,35};
   cout << (ob.largestComponentSize(v));
}

ইনপুট

{4,6,15,35}

আউটপুট

4