Formatted question description: https://leetcode.ca/all/952.html

952. Largest Component Size by Common Factor (Hard)

Given a non-empty array of unique positive integers A, consider the following graph:

• There are A.length nodes, labelled A[0] to A[A.length - 1];
• There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: [4,6,15,35]
Output: 4



Example 2:

Input: [20,50,9,63]
Output: 2



Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8



Note:

1. 1 <= A.length <= 20000
2. 1 <= A[i] <= 100000

Related Topics:
Math, Union Find

Solution 1. Union Find + Factor

The number of elements is big. Can we reduce the scale? Consider all the primes that are factors of numbers in A.

For each number A[i], we union all the factors of A[i]. In this way, A[i]s are grouped according to factors. The size of the biggest group is the result.

// OJ: https://leetcode.com/problems/largest-component-size-by-common-factor/
// Time: O(N * sqrt(W)) where N is length of A, W is max(A[i])
// Space: O(N)
class UnionFind {
vector<int> id;
public:
UnionFind(int N) : id(N) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int p = find(a), q = find(b);
if (p == q) return;
id[p] = q;
}
};
class Solution {
vector<int> factors(int n) {
vector<int> ans;
for (int i = 2; i * i <= n; ++i) {
if (n % i) continue;
ans.push_back(i);
while (n % i == 0) n /= i;
}
if (n > 1 || ans.empty()) ans.push_back(n);
return ans;
}
public:
int largestComponentSize(vector<int>& A) {
vector<vector<int>> F;
unordered_map<int, int> m;
int i = 0, ans = 0;
for (int n : A) {
auto f = factors(n);
F.push_back(f);
for (int x : f) {
if (!m.count(x)) m[x] = i++;
}
}
UnionFind uf(m.size());
for (auto &f : F) {
for (int x : f) uf.connect(m[f[0]], m[x]);
}
vector<int> cnt(m.size());
for (auto &f : F) ans = max(ans, ++cnt[uf.find(m[f[0]])]);
return ans;
}
};

• class Solution {
public int largestComponentSize(int[] A) {
int max = 0;
for (int num : A)
max = Math.max(max, num);
int[] parents = new int[max + 1];
for (int i = 0; i <= max; i++)
parents[i] = i;
for (int num : A) {
int sqrt = (int) Math.sqrt(num);
for (int i = 2; i <= sqrt; i++) {
if (num % i == 0) {
union(parents, num, i);
union(parents, num, num / i);
}
}
}
int[] counts = new int[max + 1];
int maxSize = 0;
for (int num : A) {
int ancestor = find(parents, num);
counts[ancestor]++;
maxSize = Math.max(maxSize, counts[ancestor]);
}
return maxSize;
}

public void union(int[] parents, int num1, int num2) {
int ancestor1 = find(parents, num1);
int ancestor2 = find(parents, num2);
if (ancestor1 != ancestor2)
parents[ancestor1] = ancestor2;
}

public int find(int[] parents, int num) {
while (parents[num] != num) {
parents[num] = parents[parents[num]];
num = parents[num];
}
return num;
}
}

############

class UnionFind {
int[] p;

UnionFind(int n) {
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
}

void union(int a, int b) {
int pa = find(a), pb = find(b);
if (pa != pb) {
p[pa] = pb;
}
}

int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}

class Solution {
public int largestComponentSize(int[] nums) {
int m = 0;
for (int v : nums) {
m = Math.max(m, v);
}
UnionFind uf = new UnionFind(m + 1);
for (int v : nums) {
int i = 2;
while (i <= v / i) {
if (v % i == 0) {
uf.union(v, i);
uf.union(v, v / i);
}
++i;
}
}
int[] cnt = new int[m + 1];
int ans = 0;
for (int v : nums) {
int t = uf.find(v);
++cnt[t];
ans = Math.max(ans, cnt[t]);
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/largest-component-size-by-common-factor/
// Time: O(N * sqrt(M))
// Space: O(N + sqrt(M))
class UnionFind {
vector<int> id, size;
public:
UnionFind(int N) : id(N), size(N, 1) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int p = find(a), q = find(b);
if (p == q) return;
id[p] = q;
size[q] += size[p];
}
int getSize(int a) { return size[find(a)]; }
};
class Solution {
vector<int> factors(int n) {
vector<int> ans;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) ans.push_back(i);
while (n % i == 0) n /= i;
}
if (n > 1) ans.push_back(n);
return ans;
}
public:
int largestComponentSize(vector<int>& A) {
int N = A.size(), ans = 0;
UnionFind uf(N);
unordered_map<int, int> m;  // primce factor -> a representative (the first) number with this factor
for (int i = 0; i < N; ++i) {
for (int &f : factors(A[i])) {
if (m.count(f)) uf.connect(i, m[f]);
else m[f] = i;
}
}
for (int i = 0; i < N; ++i) ans = max(ans, uf.getSize(i));
return ans;
}
};

• class UnionFind:
def __init__(self, n):
self.p = list(range(n))

def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa != pb:
self.p[pa] = pb

def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]

class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
uf = UnionFind(max(nums) + 1)
for v in nums:
i = 2
while i <= v // i:
if v % i == 0:
uf.union(v, i)
uf.union(v, v // i)
i += 1
return max(Counter(uf.find(v) for v in nums).values())

############

class Solution:
def largestComponentSize(self, A):
"""
:type A: List[int]
:rtype: int
"""
ma = max(A)
N = len(A)
m = list(range(ma + 1))
for a in A:
for k in range(2, int(math.sqrt(a)) + 1):
if a % k == 0:
self.u(m, a, k)
self.u(m, a, a // k)
count = collections.defaultdict(int)
for a in A:
count[self.f(m, a)] += 1
return max(count.values())

def f(self, m, a):
while m[a] != a:
m[a] = m[m[a]]
a = m[a]
return a

def u(self, m, a, b):
if m[a] == m[b]: return
pa = self.f(m, a)
pb = self.f(m, b)
m[pa] = pb

• func largestComponentSize(nums []int) int {
m := 0
for _, v := range nums {
m = max(m, v)
}
p := make([]int, m+1)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
union := func(a, b int) {
pa, pb := find(a), find(b)
if pa != pb {
p[pa] = pb
}
}
for _, v := range nums {
i := 2
for i <= v/i {
if v%i == 0 {
union(v, i)
union(v, v/i)
}
i++
}
}
ans := 0
cnt := make([]int, m+1)
for _, v := range nums {
t := find(v)
cnt[t]++
ans = max(ans, cnt[t])
}
return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}