C++ में कॉमन फैक्टर द्वारा सबसे बड़ा कंपोनेंट साइज

मान लीजिए कि हमारे पास अद्वितीय धनात्मक पूर्णांकों की एक सरणी A है, अब निम्नलिखित ग्राफ पर विचार करें -

कई नोड्स की लंबाई होती है, इन्हें ए [0] से ए [ए -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 के समान है, तो -

  • वापसी

• अगर रैंक [parX]>=रैंक [parY], तो −

  • रैंक [parX]:=रैंक [parX] + रैंक [parY]

  • माता-पिता [parY] :=parX

• अन्यथा

  • रैंक [parY] :=रैंक [parY] + रैंक [parX]

  • पैरेंट [parX] :=parY

• मुख्य विधि से निम्न कार्य करें -

• रिट:=0, एन:=ए का आकार

• माता-पिता:=आकार की एक सरणी को परिभाषित करें n इसे -1 से भरें

• रैंक :=आकार की एक सरणी को परिभाषित करें n इसे 1 से भरें

• एक नक्शा परिभाषित करें मी

• इनिशियलाइज़ i :=0 के लिए, जब i

  • एक्स:=ए[i]

  • इनिशियलाइज़ j :=2 के लिए, जब j * j <=x, अपडेट करें (j को 1 से बढ़ाएँ), करें -

    • यदि x mod j, 0 के समान है, तो &minsu;

      • यदि j, m में है, तो -

        • Unionn(m[j], i)

      • अन्यथा

        • एम [जे]:=मैं

      • अगर (x / j) मी में है, तो -

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

      • अन्यथा

        • एम [एक्स / जे] =मैं

  • यदि x, m में है, तो -

    • Unionn(m[x], i)

  • अन्यथा

    • एम [एक्स]:=मैं

  • रिट:=अधिकतम रिट और रैंक [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