golang union find, standard template
typical union find template can be used, we use a factor map to keep track of the most recent group belonging to that factor, it does not have to be most update
typical union find template can be used, we use a factor map to keep track of the most recent group belonging to that factor, it does not have to be most updated since we always union using the parent of the group regardless. here I say "most updated" meaning that group does not necessarily have to be the parent group, it could be a child belonging to another parent group.\n\nto consider 2 indices eligible to be union, means that the value at their index must share a common factor.\nexample, consider array: [2,3,4,5] and index 0 and 2.\nindex 0: value -> 2\nindex 2: value -> 4\nthis is considered a good pair to union because they share a common factor of 2.\n\nIf you like to visualise things as a graph, then a common factor of 2 is like an edge connecting 2 vertex/nodes representing index 0 and index 2 for the above case.\n\n\n```\nfunc largestComponentSize(nums []int) int {\n    factorMap := make(map[int]int) // factor -> number (note: store first one is good enough, we map it back to the parent group in the uf always)\n    \n    uf := NewUnionFind(len(nums))\n    for i, num := range nums {\n        for _, factor := range genFactor(num) {\n            if otherIdx, exist := factorMap[factor]; exist {\n                uf.union(i, otherIdx)\n            }\n            factorMap[factor] = i\n        }\n    }\n    \n    return uf.findLargestComponentSize()\n}\n\n// generates all factors of num, not inclusive of 1\nfunc genFactor(num int) []int {\n    res := make([]int, 0)\n    for i := 2; i<=int(math.Sqrt(float64(num))); i++ {\n        if num % i == 0 {\n            res = append(res, i)\n            if i != num/i {\n                res = append(res, num/i)\n            }\n        }\n    }\n    res = append(res, num)  // put in num itself, we do not consider 1 in the loop\n    \n    return res\n}\n\n// mapping groups by index\ntype UnionFind struct {\n    parents []int\n    size []int\n}\n\nfunc NewUnionFind(n int) *UnionFind {\n    parents := make([]int, n)\n    size := make([]int, n)\n    for i := range parents {\n        parents[i] = i\n        size[i] = 1\n    }\n    \n    return &UnionFind{parents: parents, size: size}\n}\n\nfunc (u *UnionFind) find(x int) int {\n    if u.parents[x] == x {\n        return x\n    }\n    root := u.find(u.parents[x])\n    u.parents[x] = root\n    \n    return root\n}\n\nfunc (u *UnionFind) union(x, y int) {\n    rootX := u.find(x)\n    rootY := u.find(y)\n    if rootX != rootY {\n        u.parents[rootY] = rootX\n        u.size[rootX] += u.size[rootY]\n    }\n}\n\nfunc (u *UnionFind) findLargestComponentSize() int {\n    res := 0\n    for _, s := range u.size {\n        if s > res {\n            res = s\n        }\n    }\n\n    return res\n}\n```
[]