2709. Greatest Common Divisor Traversal
幹你老師，編輯到一半跳掉，害我要重打一次
怎麼連續2天都是hard
思路 :
這題解法其實很簡單，就是當兩個數字有大於1的公因數，就把它們連接在一起
最後看是不是所有點都在同一個graph上
不過要怎麼實現就想得有點久了
一開始是將所有組合都跑過一次
不過這樣是o(n^2)，結果就是超時
最後看了一下提示
先找出最大的數字maxnum，並建立一個長度為maxnum+1的array:factor
factor裡面是放1~maxnum所有數字的最小質因數
並建立一個parent array，一開始的值跟factor是一樣的
接著將parent[nums[i]]、nums[i]所有質因數p的parent[p]的值
改成最小的parent值
最後去看parent[nums[i]]的是不是都一樣就好了
golang code
func canTraverseAllPairs(nums []int) bool {
if len(nums) == 1 {
return true
}
maxnum := nums[0]
minnum := nums[0]
for _, val := range nums[1:] {
maxnum = max(maxnum, val)
minnum = min(minnum, val)
}
if minnum == 1 {
return false
}
factor := make([]int, maxnum+1)
parent := make([]int, maxnum+1)
n := len(factor)
for i := 1; i < n; i++ {
factor[i] = i
}
for i := 2; i < n; i++ {
if factor[i] == i {
for j := i * 2; j < n; j += i {
if factor[j] == j {
factor[j] = i
}
}
}
}
copy(parent, factor)
for _, val := range nums {
temp := val
for temp > 1 {
p := factor[temp]
g1 := find(parent, val)
g2 := find(parent, temp)
if g1 != g2 {
parent[max(g1, g2)] = min(g1, g2)
}
for temp%p == 0 {
temp /= p
}
}
}
p := find(parent, parent[nums[0]])
for _, val := range nums {
if find(parent, parent[val]) != p {
return false
}
}
return true
}
func find(arr []int, i int) int {
for arr[i] != i {
i = arr[i]
}
return i
}