# Largest Component Size By Common Factor Problem

## Description

LeetCode Problem 952.

You are given an integer array of unique positive integers nums. Consider the following graph:

• There are nums.length nodes, labeled nums[0] to nums[nums.length - 1],
• There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1.

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

Example 1:

``````1
2
Input: nums = [4,6,15,35]
Output: 4
``````

Example 2:

``````1
2
Input: nums = [20,50,9,63]
Output: 2
``````

Example 3:

``````1
2
Input: nums = [2,3,6,7,4,12,21,39]
Output: 8
``````

Constraints:

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= 10^5
• All the values of nums are unique.

## Sample C++ Code using Union Find

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class UnionFindSet {
public:
UnionFindSet(int n) : _parent(n) {
for (int i=0; i<n; i++) {
_parent[i] = i;
}
}

void Union(int x, int y) {
_parent[Find(x)] = _parent[Find(y)];
}

int Find(int x) {
if (_parent[x] != x) {
_parent[x] = Find(_parent[x]);
}
return _parent[x];
}

private:
vector<int> _parent;
};

class Solution {
public:
int largestComponentSize(vector<int>& A) {
int n = *max_element(A.begin(), A.end());
UnionFindSet ufs(n+1);
for (int &a : A) {
for (int k = 2; k <= sqrt(a); k++) {
if (a % k == 0) {
ufs.Union(a, k);
ufs.Union(a, a / k);
}
}
}

unordered_map<int, int> m;
int ans = 1;
for (int &a : A) {
ans = max(ans, ++m[ufs.Find(a)]);
}
return ans;
}
};
``````