1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
# 2709. Greatest Common Divisor Traversal
"""
given a 0-indexed integer array 'nums' and you are allowed to traverse
between its indices, you can traverse between index 'i' and index 'j', 'i !=
j' if and only if 'gcd(nums[i], nums[j]) > 1' where 'gcd' is the greatest
common divisor. your task is to determine if for every pair of indices 'i'
and 'j' in 'nums' where 'i < j', there exists a sequence of traversals that
can take use from 'i' to 'j'. return true if it is possible to traverse
between all such pairs of indices or false otherwise.
"""
class Solution(object):
def canTraverseAllPairs(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = len(nums)
if n == 1:
return True
f = [_ for _ in range(0, n)]
num = [1] * n
def getf(x: int) -> int:
if f[x] == x:
return x
f[x] = getf(f[x])
return f[x]
def merge(x: int, y: int):
x, y = getf(x), getf(y)
if x == y:
return
if num[x] < num[y]:
x, y = y, x
f[y] = x
num[x] += num[y]
have = {}
for i in range(0, n):
x = nums[i]
if x == 1:
return False
d = 2
while d * d <= x:
if x % d == 0:
if d in have:
merge(i, have[d])
else:
have[d] = i
while x % d == 0:
x //= d
d += 1
if x > 1:
if x in have:
merge(i, have[x])
else:
have[x] = i
return num[getf(0)] == n
if __name__ == "__main__":
obj = Solution()
print(obj.canTraverseAllPairs([2, 3, 6]))
print(obj.canTraverseAllPairs([3, 9, 5]))
print(obj.canTraverseAllPairs([4, 3, 12, 8]))
|