<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>, and you are allowed to <strong>traverse</strong> between its indices. You can traverse between index <code>i</code> and index <code>j</code>, <code>i != j</code>, if and only if <code>gcd(nums[i], nums[j]) &gt; 1</code>, where <code>gcd</code> is the <strong>greatest common divisor</strong>.</p>

<p>Your task is to determine if for <strong>every pair</strong> of indices <code>i</code> and <code>j</code> in nums, where <code>i &lt; j</code>, there exists a <strong>sequence of traversals</strong> that can take us from <code>i</code> to <code>j</code>.</p>

<p>Return <code>true</code><em> if it is possible to traverse between all such pairs of indices,</em><em> or </em><code>false</code><em> otherwise.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,3,6]
<strong>Output:</strong> true
<strong>Explanation:</strong> In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2).
To go from index 0 to index 1, we can use the sequence of traversals 0 -&gt; 2 -&gt; 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 &gt; 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 &gt; 1.
To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 &gt; 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 &gt; 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,9,5]
<strong>Output:</strong> false
<strong>Explanation:</strong> No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,3,12,8]
<strong>Output:</strong> true
<strong>Explanation:</strong> There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        # solution redone here, original solutions further below
        n, m = len(nums), max(nums)
        idx_to_factor = collections.defaultdict(list)
        factor_to_idx = collections.defaultdict(list)
        for i in range(n):
            num = nums[i]
            temp = num
            # this for loop works because we can have at most one prime factor larger than sqrt(num)
            for prime_factor in range(2, math.ceil(num ** (1/2)) + 1):
                if temp % prime_factor > 0:
                    continue
                while temp % prime_factor == 0:
                    temp = temp // prime_factor
                idx_to_factor[i].append(prime_factor)
                factor_to_idx[prime_factor].append(i)
            # this could be (if it exists) the singular prime factor that is larger than sqrt(num)
            if temp > 1:
                idx_to_factor[i].append(temp)
                factor_to_idx[temp].append(i)
        
        graph = collections.defaultdict(list)
        for prime_factor in factor_to_idx:
            idx_list = factor_to_idx[prime_factor]
            first_idx = idx_list[0]
            for i in range(1, len(idx_list)):
                graph[first_idx].append(idx_list[i])
                graph[idx_list[i]].append(first_idx)

        def dfs(u):
            for v in graph[u]:
                if v not in seen:
                    seen.add(v)
                    dfs(v)
        
        seen = set([0])
        dfs(0)
        return len(seen) == n
















        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    #     """Solution 1:"""
    #     if len(nums) == 1:
    #         return True
    #     nums = list(set(nums))
    #     if 1 in nums:
    #         return False
    #     self.prime2index = collections.defaultdict(list)
    #     self.index2prime = collections.defaultdict(list)
    #     for i, num in enumerate(nums):
    #         temp = num
    #         for prime in range(2, math.ceil(num ** (1/2)) + 1):
    #             added = False
    #             # the prime factorization of num could have the number prime appear many
    #             # times, and so we remove all these occurrences
    #             # note that after the termination of the while loop, temp cannot be divisible
    #             # by any (prime or composite number) that is divisible by prime
    #             while temp > 1 and temp % prime == 0:
    #                 if not added:
    #                     self.index2prime[(i, "num")].append((prime, "prime"))
    #                     self.prime2index[(prime, "prime")].append((i, "num"))
    #                     added = True
    #                 temp = temp // prime
    #             # if below is true, then we have already obtained all prime factors
    #             if temp == 1:
    #                 break
    #         # the key point is that if the below clause is true, then temp is prime
    #         # the reason is because if temp is not prime, then temp >= p*q for
    #         # two (possibly) same primes p and q. Assume WLOG that p <= q. then
    #         # num >= temp >= p*q >= p^2. thus we have that sqrt(num) >= p, which is
    #         # a contradiction because in the above for loop we iterate over all possible
    #         # primes till the sqrt(num), which implies that we would have considered
    #         # p as a prime factor and hence temp would not have been divisible by p
    #         # after the completion of the for loop. thus temp must be prime.
    #         if temp > 1:
    #             prime = temp
    #             self.index2prime[(i, "num")].append((prime, "prime"))
    #             self.prime2index[(prime, "prime")].append((i, "num"))

    #     # we now have the graph (similar to how we have it in Solution 2, and just run DFS)
    #     def dfs(curr, visited, is_num_node):
    #         if is_num_node:
    #             neighbors = self.index2prime[curr]
    #         else:
    #             neighbors = self.prime2index[curr]
    #         for v in neighbors:
    #             if v not in visited:
    #                 visited.add(v)
    #                 dfs(v, visited, not is_num_node)

    #     visited = set([(0, "num")])
    #     dfs((0, "num"), visited, True)
    #     for i in range(len(nums)):
    #         if (i, "num") not in visited:
    #             return False
    #     return True
        
    #     """Solution 2:"""
    #     # the official solution is useful
    #     # we would like to draw an edge between two numbers in nums if their GCD > 1
    #     # and then check for a singular connected component
    #     # but this can have n^2 edges
    #     # instead note that gcd(x, y) > 1 if and only if x,y share a prime factor
    #     # we make a graph where there are n + k vertices, where n = len(nums)
    #     # and k is the number of unique prime factors of all numbers in nums
    #     # for each vertex corresponding to a number in nums, draw an edge to
    #     # each of its prime factors
    #     # note that any two of the n vertices (that correspond to numbers in nums)
    #     # are connected if and only if there is a sequence of the n vertices where adjacent
    #     # vertices in the sequence share a prime factor (and of course where the start and
    #     # end vertices of the sequence are the two vertices we are looking at)
    #     # and since gcd(x, y) > 1 if and only if x,y share a prime factor, we can simply
    #     # check for the existence of a single connected component on this graph
    #     # this solution is correct, but results in TLE
        
    #     # if len(nums) == 1:
    #     #     return True
    #     # if 1 in nums:
    #     #     return False
    #     # nums = list(set(nums))

    #     # m = max(nums)

    #     # primes = [True] * (m + 1)
    #     # for i in range(2, m + 1):
    #     #     if not primes[i]:
    #     #         continue
    #     #     j = i * i
    #     #     while j <= m:
    #     #         primes[j] = False
    #     #         j += i
    #     # primes = [i for i in range(2, m + 1) if primes[i]]

    #     # def find(x, parents):
    #     #     if x == parents[x]:
    #     #         return x
    #     #     res = find(parents[x], parents)
    #     #     parents[x] = res
    #     #     return res
        
    #     # def union(x, y, parents, ranks):
    #     #     anc_x = find(x, parents)
    #     #     anc_y = find(y, parents)
    #     #     if anc_x == anc_y:
    #     #         return
    #     #     if ranks[x] < ranks[y]:
    #     #         parents[anc_x] = anc_y
    #     #     elif ranks[x] > ranks[y]:
    #     #         parents[anc_y] = anc_x
    #     #     else:
    #     #         parents[anc_y] = anc_x
    #     #         ranks[anc_x] += 1

    #     # n = len(nums)
    #     # parents = [i for i in range(n + len(primes))]
    #     # ranks = [1] * (n + len(primes))

    #     # for i, num in enumerate(nums):
    #     #     for j, p in enumerate(primes):
    #     #         if p > num:
    #     #             break
    #     #         if num % p == 0:
    #     #             union(i, j + n, parents, ranks)

    #     # anc = find(0, parents)
    #     # for i in range(1, n):
    #     #     if find(i, parents) != anc:
    #     #         return False
    #     # return True

    #     """Solution 3:"""
    # # below solution builds smaller graph and is borrowed from
    # # https://leetcode.com/problems/greatest-common-divisor-traversal/solutions/4780257/2-fast-solutions-and-their-intuition/

    # # if len(nums) == 1:
    #     #     return True
    #     # if 1 in nums:
    #     #     return False
    #     # nums = set(nums)
    #     # m = max(nums)
    #     # primes = [True] * (m + 1)
    #     # for i in range(2, m + 1):
    #     #     if not primes[i]:
    #     #         continue
    #     #     j = i * i
    #     #     while j <= m:
    #     #         primes[j] = False
    #     #         j += i
    #     # primes = [i for i in range(2, m + 1) if primes[i]]
        
    #     # graph = collections.defaultdict(list)
    #     # for num in nums:
    #     #     factors = []
    #     #     for p in primes:
    #     #         if p > num:
    #     #             break
    #     #         if num % p == 0:
    #     #             factors.append(p)
    #     #     for i in range(len(factors)):
    #     #         for j in range(i, len(factors)):
    #     #             graph[factors[i]].append(factors[j])
    #     #             graph[factors[j]].append(factors[i])
        
    #     # def dfs(curr, visited):
    #     #     for v in graph[curr]:
    #     #         if v not in visited:
    #     #             visited.add(v)
    #     #             dfs(v, visited)

    #     # if not graph:
    #     #     return False
    #     # start = list(graph.keys())[0]
    #     # visited = set([start])
    #     # dfs(start, visited)

    #     # return len(visited) == len(graph.keys())
3872