<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 DJSet:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [1 for i in range(n)]
    
    def find_parent(self, i):
        if self.parent[i]==i: return i
        self.parent[i] = self.find_parent(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        pi = self.find_parent(i)
        pj = self.find_parent(j)
        if pi==pj: return
        pi_rank = self.rank[pi]
        pj_rank = self.rank[pj]
        if pi_rank>pj_rank:
            self.parent[pj] = pi
        elif pi_rank<pj_rank:
            self.parent[pi] = pj
        else:
            self.parent[pj] = pi
            self.rank[pi]+=1

class Solution:

    def gcd(self, i, j):
        while j!=0:
            temp = i
            i = j
            j = temp%j
        return i

    # Will time out
    def canTraverseAllPairs1(self, nums: List[int]) -> bool:
        nums_len = len(nums)
        dj_set = DJSet(nums_len)
        for i in range(nums_len):
            for j in range(i+1, nums_len):
                gcd_ij = self.gcd(nums[i], nums[j])
                # print(f'{nums[i]=} {nums[j]=} {gcd_ij=}')
                if gcd_ij>1:
                    dj_set.union(i, j)
        # print(f"{dj_set.parent=}")
        # print(f"{dj_set.rank=}")
        root_count = 0
        for i in range(nums_len):
            if dj_set.find_parent(i)!=root:
                root_count+=1
                if root_count>1: return False
        return True
    
    def get_all_factors(self, num):
        factors = set()
        a = 1
        b = sqrt(num)
        while a<=b:
            if (num%a)==0:
                factors.add(a)
                factors.add(num//a)
            a+=1
        # print(f'{num=} {factors=}')
        return factors

    # This will also time out
    def canTraverseAllPairs2(self, nums: List[int]) -> bool:
        factors_map = dict()
        unique_nums = list()
        for num in nums:
            if num not in factors_map:
                factors_map[num] = self.get_all_factors(num)
                unique_nums.append(num)
        # if 1 in factors_map: return False # Fails for [1]
        unique_nums_len = len(unique_nums)
        dj_set = DJSet(unique_nums_len)
        for i in range(unique_nums_len):
            num_i_factors = factors_map.get(unique_nums[i])
            for j in range(unique_nums_len):
                num_j_factors = factors_map.get(unique_nums[j])
                if num_i_factors.intersection(num_j_factors)!={1}:
                    dj_set.union(i, j)
        # print(f"{dj_set.parent=}")
        # print(f"{dj_set.rank=}")
        root_count = 0
        for i in range(unique_nums_len):
            if dj_set.find_parent(i)!=root:
                root_count+=1
                if root_count>1: return False
        return True
    
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        nums_len = len(nums)
        factors_map = dict()
        for num in nums:
            if num not in factors_map:
                factors_map[num] = self.get_all_factors(num)
        first_occ_of_factor = dict()
        dj_set = DJSet(nums_len)
        for i in range(nums_len):
            for factor in factors_map.get(nums[i]):
                if factor==1: continue
                if factor not in first_occ_of_factor:
                    first_occ_of_factor[factor] = i
                else:
                    dj_set.union(i, first_occ_of_factor[factor])
        # print(f'{first_occ_of_factor=}')
        # print(f"{dj_set.parent=}")
        # print(f"{dj_set.rank=}")
        root_count = 0
        for i in range(nums_len):
            if dj_set.find_parent(i)==i:
                root_count+=1
                if root_count>1: return False
        return True
2740