2021-08-02：按公因数计算最大组件大小。给定一个由不同正整数的组成的非空数组 A，考虑下面的图：有 A.length 个节点，按从 A[0] 到 A[A.length - 1] 标记；只有当 A[i] 和 A[j] 共用一个大于 1 的公因数时，A[i] 和 A[j] 之间才有一条边。返回图中最大连通组件的大小。
福大大 答案2021-08-02：
算出每个的公因数，然后并查集。
时间复杂度： O(N*sqrt(V))。
空间复杂度： O(N)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
arr := []int{2, 3, 6, 7, 4, 12, 21, 39}
ret := largestComponentSize2(arr)
fmt.Println(ret)
}
func largestComponentSize2(arr []int) int {
N := len(arr)
// arr中，N个位置，在并查集初始时，每个位置自己是一个集合
unionFind := NewUnionFind(N)
// key 某个因子 value 哪个位置拥有这个因子
fatorsMap := make(map[int]int)
for i := 0; i < N; i++ {
num := arr[i]
// 求出根号N， -> limit
limit := int(math.Sqrt(float64(num)))
for j := 1; j <= limit; j++ {
if num%j == 0 {
if j != 1 {
if _, ok := fatorsMap[j]; !ok {
fatorsMap[j] = i
} else {
unionFind.union(fatorsMap[j], i)
}
}
other := num / j
if other != 1 {
if _, ok := fatorsMap[other]; !ok {
fatorsMap[other] = i
} else {
unionFind.union(fatorsMap[other], i)
}
}
}
}
}
return unionFind.maxSize()
}
// O(1)
// m,n 要是正数，不能有任何一个等于0
func gcd(a int, b int) int {
if b == 0 {
return a
} else {
return gcd(b, a%b)
}
}
type UnionFind struct {
parents []int
sizes []int
help []int
}
func NewUnionFind(N int) *UnionFind {
res := &UnionFind{}
res.parents = make([]int, N)
res.sizes = make([]int, N)
res.help = make([]int, N)
for i := 0; i < N; i++ {
res.parents[i] = i
res.sizes[i] = 1
}
return res
}
func (this *UnionFind) maxSize() int {
ans := 0
for _, size := range this.sizes {
ans = getMax(ans, size)
}
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
func (this *UnionFind) find(i int) int {
hi := 0
for i != this.parents[i] {
this.help[hi] = i
hi++
i = this.parents[i]
}
for hi--; hi >= 0; hi-- {
this.parents[this.help[hi]] = i
}
return i
}
func (this *UnionFind) union(i int, j int) {
f1 := this.find(i)
f2 := this.find(j)
if f1 != f2 {
big := twoSelectOne(this.sizes[f1] >= this.sizes[f2], f1, f1)
small := twoSelectOne(big == f1, f2, f1)
this.parents[small] = big
this.sizes[big] = this.sizes[f1] + this.sizes[f2]
}
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}
执行结果如下：