資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中按公因數計算最大元件大小
假設我們有一個包含唯一正整數的陣列A，現在考慮以下圖：
有A的長度個節點，這些節點標記為A[0]到A[A.size()-1]；當A[i]和A[j]擁有大於1的公因數時，A[i]和A[j]之間存在一條邊。我們需要找到圖中最大連通分量的規模。
因此，如果輸入類似於[4,6,15,35]，則輸出為4。
為了解決這個問題，我們將遵循以下步驟：
定義一個數組parent
定義一個數組rank
定義一個數組rank
如果parent[x]等於-1，則：
返回x
返回parent[x] = getParent(parent[x])
定義一個函式unionn()，它將接收x, y作為引數：
parX := getParent(x)
parY := getParent(y)
如果parX等於parY，則：
返回
如果rank[parX] >= rank[parY]，則：
rank[parX] := rank[parX] + rank[parY]
parent[parY] := parX
否則
rank[parY] := rank[parY] + rank[parX]
parent[parX] := parY
在主方法中執行以下操作：
ret := 0, n := A的長度
parent := 定義一個大小為n的陣列，並將其填充為-1
rank := 定義一個大小為n的陣列，並將其填充為1
定義一個map m
for i := 0; i < n; i++ do:
x := A[i]
for j := 2; j * j <= x; j++ do:
如果x mod j 等於 0，則：
如果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
瀏覽量：113
