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）
如果xmodj与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