Problem statement

https://leetcode.com/problems/graph-connectivity-with-threshold/

Solution

We just need to create graph with connecteion for every step > treshold. Imagine, that it is equal to 1, then we need connections:

3 - 6 - 9 - ...

4 - 8 - 12 - ...

Ans so on. There swill be not a big number of connections: in fact it will be no more than n//2 + n//3 + ... = O(n log n). Then we use dsu to check connectivity.

Complexity

Time complexity is O(n log n + m log n), space is O(n).

Code

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def areConnected(self, n, T, queries):
        dsu = DSU(n + 1)
        for step in range(T + 1, n):
            for i in range(step, n+1-step, step):
                dsu.union(i, i + step)
                
        return [dsu.find(x) == dsu.find(y) for x,y in queries]