ขนาดส่วนประกอบที่ใหญ่ที่สุดตามปัจจัยร่วมใน C++

สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็มบวกเฉพาะ พิจารณากราฟต่อไปนี้ −

มีจำนวนโหนดที่มีความยาว A[0] ถึง A[ขนาด A - 1] มีขอบระหว่าง A[i] และ A[j] เมื่อ A[i] และ A[j] มีปัจจัยร่วมมากกว่า 1 เราต้องหาขนาดขององค์ประกอบที่เชื่อมต่อที่ใหญ่ที่สุดในกราฟ

ดังนั้นหากอินพุตเป็น [4,6,15,35] ผลลัพธ์จะเป็น 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดพาเรนต์อาร์เรย์

• กำหนดอันดับอาร์เรย์

• กำหนดอันดับอาร์เรย์

• ถ้า parent[x] เหมือนกับ -1 แล้ว −

  • ผลตอบแทน x

• ส่งคืนพาเรนต์[x] =getParent(พาเรนต์[x])

• กำหนดฟังก์ชัน unionn() ซึ่งจะใช้ x, y,

• parX :=getParent(x)

• parY :=getParent(y)

• ถ้า parX เหมือนกับ parY ดังนั้น −

  • กลับ

• ถ้า rank[parX]>=rank[parY] แล้ว −

  • อันดับ[parX] :=อันดับ[parX] + อันดับ[parY]

  • ผู้ปกครอง[parY] :=parX

• มิฉะนั้น

  • อันดับ[parY] :=อันดับ[parY] + อันดับ[parX]

  • parent[parX] :=parY

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ret :=0, n :=ขนาดของ A

• parent :=กำหนดขนาดอาร์เรย์ n เติมด้วย -1

• rank :=กำหนดอาร์เรย์ขนาด n เติมด้วย 1

• กำหนดหนึ่งแผนที่ m

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • x :=A[i]

  • สำหรับการเริ่มต้น j :=2 เมื่อ j * j <=x อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ -

    • ถ้า x mod j เท่ากับ 0 แล้ว &minsu;

      • ถ้า j อยู่ใน m แล้ว −

        • ยูเนียน(m[j], ผม)

      • มิฉะนั้น

        • m[j] :=ผม

      • ถ้า (x / j) อยู่ในหน่วย m แล้ว −

        • ยูเนียน(m[x / j], ผม)

      • มิฉะนั้น

        • ม[x / j] =ผม

  • ถ้า x เป็น m แล้ว −

    • ยูเนียน(m[x], ผม)

  • มิฉะนั้น

    • ม[x] :=ผม

  • 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