题目描述
给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：
有 nums.length 个节点，按从 nums[0] 到 nums[nums.length – 1] 标记；
只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。
返回 图中最大连通组件的大小 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/largest-component-size-by-common-factor
提示：
1
题目分析
最直接的想法是去遍历数组中的每一个数num。对于每一个数，可以考查其所有因子，并使用并查集将因子与这个数本身归为一个集合中，在这个过程中，数组中具有大于1的num之间也会被合并入相同的集合。最后，我们可以重新遍历nums数组，并通过并查集查询每个num对应的root，并统计对应的频次，保留最大的频次，就可以得到最大联通组件的大小。
代码
golang
type Union struct {
parent, rank []int
//rank按秩合并
}
func newUnion(n int) Union {
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
return Union{parent, make([]int, n)}
}
func (u Union) find(x int) int {
if u.parent[x] != x {
//路径压缩
u.parent[x] = u.find(u.parent[x])
}
return u.parent[x]
}
func (u Union) merge(x int, y int) {
rootX := u.find(x)
rootY := u.find(y)
if rootX != rootY {
if u.rank[rootY] > u.rank[rootX] {
u.parent[rootX] = rootY
} else if u.rank[rootY] > u.rank[rootX] {
u.parent[rootY] = rootX
} else {
u.parent[rootX] = rootY
//更新秩
u.rank[rootY]++
}
}
}
func max(x int, y int) int{
if x > y {
return x
}
return y
}
func largestComponentSize(nums []int) int {
maxVal := 0
for _, num := range nums{
maxVal = max(num, maxVal)
}
union := newUnion(maxVal +1)
for _, num := range nums{
//暴力筛
for i := 2; i * i <= num; i++{ if num % i="=" 0{ union.merge(num, i) } rtn :="0" arr maxval+1) for _, nums{ root arr[root] ++ arr[root]) return < code></=>
Original: https://www.cnblogs.com/xy1997/p/16536221.html
Author: xingyuanyuan
Title: [LC952]按公因数计算最大组件大小
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588088/
转载文章受原作者版权保护。转载请注明原作者出处！