C++의 공통 요소별 최대 구성 요소 크기

고유한 양의 정수로 구성된 배열 A가 있다고 가정하고 이제 다음 그래프를 고려하십시오. -

A 길이의 노드가 여러 개 있으며 A[0]에서 A[A - 1의 크기]까지 레이블이 지정됩니다. A[i]와 A[j]가 1보다 큰 공약수를 공유할 때 A[i]와 A[j] 사이에 간선이 있습니다. 그래프에서 가장 큰 연결 성분의 크기를 찾아야 합니다.

따라서 입력이 [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]이면 -

  • 순위[parX] :=순위[parX] + 순위[parY]

  • 부모[parY] :=parX

• 그렇지 않으면

  • 순위[parY] :=순위[parY] + 순위[parX]

  • 부모[parX] :=parY

• 주요 방법에서 다음을 수행하십시오 -

• ret :=0, n :=A의 크기

• parent :=크기가 n인 배열을 -1로 채우십시오.

• rank :=n 크기의 배열을 정의하고 1로 채웁니다.

• 하나의 맵 정의

• initialize i :=0의 경우, i

  • x :=A[i]

  • j를 초기화하기 위해 :=2, j * j <=x일 때 업데이트(j를 1만큼 증가), −

    • x mod j가 0과 같으면 &minsu;

      • j가 m에 있으면 -

        • 결합(m[j], i)

      • 그렇지 않으면

        • m[j] :=나는

      • (x / j)가 m인 경우 -

        • 유니온(m[x / j], i)

      • 그렇지 않으면

        • m[x/j] =i

  • x가 m이면 -

    • 결합(m[x], i)

  • 그렇지 않으면

    • m[x] :=나는

  • ret :=ret 및 rank의 최대값[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