C++の公約数による最大コンポーネントサイズ

一意の正の整数の配列Aがあるとします。次に、次のグラフを検討します-

A個のノードの長さがあり、これらにはA[0]からA[Aのサイズ-1]のラベルが付いています。 A[i]とA[j]が1より大きい共通因子を共有する場合、A[i]とA[j]の間にエッジがあります。グラフで最大連結成分のサイズを見つける必要があります。

したがって、入力が[4,6,15,35]の場合、出力は4

これを解決するには、次の手順に従います-

• 配列の親を定義する

• 配列ランクを定義する

• 配列ランクを定義する

• parent [x]が-1と同じ場合、-

  • xを返す

• return parent [x] =getParent（parent [x]）

• 関数unionn（）を定義します。これには、x、y、

  が必要です。

• parX：=getParent（x）

• parY：=getParent（y）

• parXがparYと同じ場合、-

  • 戻る

• ランク[parX]>=ランク[parY]の場合、-

  • ランク[parX]：=ランク[parX]+ランク[parY]

  • parent [parY]：=parX

• それ以外の場合

  • ランク[parY]：=ランク[parY]+ランク[parX]

  • parent [parX]：=parY

• メインの方法から、次のようにします-

• ret：=0、n：=Aのサイズ

• 親：=サイズnの配列を定義しますこれを-1で埋めます

• ランク：=サイズnの配列を定義しますこれを1で埋めます

• 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とrankの最大値[getParent（i）]

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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