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

Giả sử chúng ta có một mảng A gồm các số nguyên dương duy nhất, bây giờ hãy xem xét đồ thị sau -

Có độ dài của một số nút, chúng được gắn nhãn A [0] đến A [kích thước của A - 1]; Có một cạnh giữa A [i] và A [j] khi A [i] và A [j] có chung nhân tử lớn hơn 1. Chúng ta phải tìm kích thước của thành phần liên thông lớn nhất trong đồ thị.

Vì vậy, nếu đầu vào là [4,6,15,35], thì đầu ra sẽ là 4

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định mảng cha mẹ
Xác định thứ hạng mảng
Xác định thứ hạng mảng
nếu cha [x] giống -1, thì -
- trả lại x
return cha [x] =getParent (cha [x])
Xác định một hàm unionn (), hàm này sẽ lấy x, y,
parX:=getParent (x)
parY:=getParent (y)
nếu parX giống như parY, thì -
- trở lại
nếu rank [parX]> =rank [parY] thì -
- rank [parX]:=rank [parX] + rank [parY]
- cha [parY]:=parX
Nếu không
- rank [parY]:=rank [parY] + rank [parX]
- cha [parX]:=parY
Từ phương thức chính, hãy làm như sau -
ret:=0, n:=kích thước của A
cha:=Xác định một mảng có kích thước n điền vào giá trị này bằng -1
rank:=Xác định một mảng có kích thước n điền vào đây là 1
Xác định một bản đồ m
để khởi tạo i:=0, khi i
- x:=A [i]
- để khởi tạo j:=2, khi j * j <=x, cập nhật (tăng j lên 1), thực hiện -
  - nếu x mod j giống 0, thì &minsu;
    - nếu j tính bằng m thì -
      - unionn (m [j], i)
    - Nếu không
      - m [j]:=i
    - nếu (x / j) tính bằng m, thì -
      - unionn (m [x / j], i)
    - Nếu không
      - m [x / j] =i
- nếu x tính bằng m thì -
  - unionn (m [x], i)
- Nếu không
  - m [x]:=i
- ret:=tối đa ret và xếp hạng [getParent (i)]
trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{4,6,15,35}

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

Ví dụ

Đầu vào

Đầu ra