【Leetcode952】按公因数计算最大组件大小

题干

给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：

有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。

返回 图中最大连通组件的大小 。

解题思路

有连通查找可以想到并查集，公因数就常见思路gcd函数计算就行，常规题型的变体

思路拆解

并查集（Union-Find）：

使用并查集来管理连通组件。

对于每个数，找到它的所有质因数，并将这些质因数与数本身合并到同一个集合中。

最终，统计每个集合的大小，返回最大值。

质因数分解：

对于每个数，分解出它的所有质因数。

将这些质因数作为桥梁，将具有相同质因数的数合并到同一个集合中。

源码：

并查集模板

class UnionFind { int[] parent; int[] rank; public UnionFind(int n) { parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } rank = new int[n]; } public void union(int x, int y) { int rootx = find(x); int rooty = find(y); if (rootx != rooty) { if (rank[rootx] > rank[rooty]) { parent[rooty] = rootx; } else if (rank[rootx] < rank[rooty]) { parent[rootx] = rooty; } else { parent[rooty] = rootx; rank[rootx]++; } } } public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } }

 题解：

public int largestComponentSize(int[] nums) { int m = Arrays.stream(nums).max().getAsInt(); UnionFind uf = new UnionFind(m + 1); for (int num : nums) { for (int i = 2; i * i <= num; i++) { if (num % i == 0) { uf.union(num, i); uf.union(num, num / i); } } } int[] counts = new int[m + 1]; int ans = 0; for (int num : nums) { int root = uf.find(num); counts[root]++; ans = Math.max(ans, counts[root]); } return ans; } }