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 mainimport (    "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 要是正数，不能有任何一个等于0func 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    }}

执行结果如下：

***

[左神java代码]()