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

• 返回parent [x] = getParent（parent [x]）

• 定义一个函数unionn()，它将取x，y，

• parX：= getParent(x)

• parY：= getParent(y)

• 如果parX与parY相同，则-

• 返回

• 如果rank [parX]> = rank [parY]，则-

• 等级[parX]：=等级[parX] +等级[parY]

• parent [parY]：= parX

• 除此以外

• 等级[parY]：=等级[parY] +等级[parX]

• parent [parX]：= parY

• 从主要方法中执行以下操作-

• ret：= 0，n：= A的大小

• parent：=定义一个大小为n的数组，用-1填充

• rank：=定义一个大小为n的数组，用1填充

• 定义一张映射

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• m [x]：= i

• unionn（m [x]，i）

• 如果x mod j与0相同，则＆minsu;

• m [x / j] = i

• unionn（m [x / j]，i）

• m [j]：= i

• unionn（m [j]，i）

• 如果j在m中，则-

• 除此以外

• 如果（x / j）以m为单位，则-

• 除此以外

• x：= A [i]

• 对于初始化j：= 2，当j * j <= x时，更新（将j增加1），执行-

• 如果x以m为单位，则-

• 除此以外

• 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