Python| Union-Find| Sorting
\n# Idea: \n# For a query [p, q, limit]\n# we can connect all edges with a weight less than limit -> union nodes u_i, v_i if dis_i < limit\n# after previous ste
```\n# Idea: \n# For a query [p, q, limit]\n# we can connect all edges with a weight less than limit -> union nodes u_i, v_i if dis_i < limit\n# after previous step, simply check if p and q is connected  ---> get answer for this query\n\n# Optimization: \n# we can sort the query in ASC by limit, so for query with larger limits, no need to connect small weight edges\n\n\nclass Solution:\n    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:\n        \n        # Dynamic union-find with path compression and union by rank\n        class UnionFind:\n\t\t    pass\n        \n        edgeList.sort(key=lambda x:x[2])        # sort all edges by weight("distance")\n        for i in range(len(queries)):\n            queries[i].append(i)                # add original query index into query cuz we will sort it later\n                                                # we still need original index to store answers\n            \n        queries.sort(key=lambda x:x[2])         # sort the query in ASC by limit\n        uf = UnionFind()\n        start = 0                               # record start index of unvisited edge in edgeList\n        ans = [False] * len(queries)\n        \n        for u, v, limit, index in queries:\n            \n            for i in range(start, len(edgeList)):\n                a, b, weight = edgeList[i]\n                if weight < limit:\n                    uf.union(a, b)\n                else:                           # find an edge with weiight >= limit, stop here\n                    start = i                   # record current index, so we can resume more efficiently \n                    break\n            \n            if u in uf.parents and v in uf.parents and uf.find(u) == uf.find(v):\n                ans[index] = True\n                \n        return ans \n```\n\nImplementation of UnionFind class in more details: \nWe don\'t always need path compression and union-by-rank, but it doesn\'t hurt if we implement that.\n\n```\n# Dynamic union-find with path compression and union by rank\n        class UnionFind:\n            def __init__(self):\n                self.parents = {}\n                self.ranks = {}\n                \n            def insert(self, x):\n                if x not in self.parents:\n                    self.parents[x] = x\n                    self.ranks[x] = 0\n                \n            def find(self, x):\n                if self.parents[x] != x:\n                    self.parents[x] = self.find(self.parents[x])\n                return self.parents[x]\n            \n            def union(self, x, y):\n                self.insert(x)\n                self.insert(y)\n                x, y = self.find(x), self.find(y)\n                if x == y:\n                    return \n                if self.ranks[x] > self.ranks[y]:\n                    self.parents[y] = x\n                else:\n                    self.parents[x] = y\n                    if self.ranks[x] == self.ranks[y]:\n                        self.ranks[y] += 1\n```
['Union Find', 'Sorting', 'Python']