0900 - 0999
0952 - Largest Component Size by Common Factor (Hard)
Problem Link
https://leetcode.com/problems/largest-component-size-by-common-factor
Problem Statement
You are given an integer array of unique positive integers nums. Consider the following graph:
- There are
nums.lengthnodes, labelednums[0]tonums[nums.length - 1], - There is an undirected edge between
nums[i]andnums[j]ifnums[i]andnums[j]share a common factor greater than1.
Return the size of the largest connected component in the graph.
Example 1:
Input: nums = [4,6,15,35]
Output: 4Example 2:
Input: nums = [20,50,9,63]
Output: 2Example 3:
Input: nums = [2,3,6,7,4,12,21,39]
Output: 8Constraints:
1 <= nums.length <= 2 * 10^41 <= nums[i] <= 1e5- All the values of
numsare unique.
Approach 1: Factorisation + DSU
We iterate each number and factorise it. In general, here's the approach.
vector<int> factorize(int x) {
vector<int> res;
for (int y = 2; y * y <= x; y++) {
if (x % y) continue;
while(x % y == 0) {
res.push_back(y);
x /= y;
}
}
if (x > 1) res.push_back(x);
return res;
}Once we got the factors, we use DSU to unite each factor and the number.
class dsu {
public:
vector<int> root, rank, size;
int n;
int cnt;
dsu(int _n) : n(_n) {
root.resize(n);
rank.resize(n);
size.resize(n);
for(int i = 0; i < n; i++) {
root[i] = i;
rank[i] = 1;
size[i] = 1;
}
cnt = n;
}
inline int getCount() { return cnt; }
inline int get(int x) { return (x == root[x] ? x : (root[x] = get(root[x]))); }
inline bool unite(int x, int y) {
x = get(x); y = get(y);
if (x != y) {
if (rank[x] > rank[y]) {
root[y] = x;
} else if (rank[x] < rank[y]) {
root[x] = y;
} else {
root[y] = x;
rank[x] += 1;
}
cnt--;
return true;
}
return false;
}
};At the end, we check the size of each group and return the max one.
int largestComponentSize(vector<int>& nums) {
int n = nums.size();
dsu d(100005);
for (auto x : nums) {
// step 1: factorize each number
vector<int> f = factorize(x);
// step 2: unite each number with its factors
for (int i = 0; i < f.size(); i++) {
d.unite(x, f[i]);
}
}
// step 3: find out the max group size
int ans = 0;
unordered_map<int, int> m;
for (auto x : nums) {
ans = max(ans, ++m[d.get(x)]);
}
return ans;
}