C ++中因公因数最大的组件大小

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个唯一的正整数数组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

    以上是 C ++中因公因数最大的组件大小 的全部内容， 来源链接： utcz.com/z/335194.html

    回到顶部