[Python] Union-Find
Intuition:\n\n- Since one of the constraints is 1 <= edgeList.length, queries.length <= 10^5 so O(N^2) solution won\'t pass, we need to be better than that\n- D
Intuition:\n\n- Since one of the constraints is `1 <= edgeList.length, queries.length <= 10^5` so `O(N^2)` solution won\'t pass, we need to be better than that\n- Disjoint Set Union is a great way to find if paths exist (if two nodes are connected)\n- To brute-force, for every query we can generate a DSU using edges smaller than the limit\n- To avoid repeated computation, if we can rearrange the queries from smaller limit to greater limit, we can build the DSU from the smaller distances to greater ones, and generate the desired answers iteratively.\n\n```python\nclass DSU:\n    def __init__(self, N):\n        self.root = list(range(N))\n    def find(self, x):\n        if self.root[x] != x:\n            self.root[x] = self.find(self.root[x])\n        return self.root[x]\n    def union(self, x, y):\n        x, y = self.find(x), self.find(y)\n        self.root[x] = self.root[y] = min(x, y)\n    def connected(self, x, y):\n        x, y = self.find(x), self.find(y)\n        return x == y\n\nclass Solution:\n    def distanceLimitedPathsExist(self, N: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:\n        Q = len(queries)\n        E = len(edgeList)\n        edgeList.sort(key=lambda x: x[2])\n        dsu = DSU(N)\n        \n        ans = [None] * Q\n        j = 0\n        \n        for l, a, b, i in sorted(((l, a, b, i) for i, (a, b, l) in enumerate(queries))):\n            while j < E and edgeList[j][2] < l:\n                x, y, _ = edgeList[j]\n                dsu.union(x, y)\n                j += 1\n            \n            ans[i] = dsu.connected(a, b)\n        \n        return ans\n```
[]