<p>An undirected graph of <code>n</code> nodes is defined by <code>edgeList</code>, where <code>edgeList[i] = [u<sub>i</sub>, v<sub>i</sub>, dis<sub>i</sub>]</code> denotes an edge between nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> with distance <code>dis<sub>i</sub></code>. Note that there may be <strong>multiple</strong> edges between two nodes.</p>

<p>Given an array <code>queries</code>, where <code>queries[j] = [p<sub>j</sub>, q<sub>j</sub>, limit<sub>j</sub>]</code>, your task is to determine for each <code>queries[j]</code> whether there is a path between <code>p<sub>j</sub></code> and <code>q<sub>j</sub></code><sub> </sub>such that each edge on the path has a distance <strong>strictly less than</strong> <code>limit<sub>j</sub></code> .</p>

<p>Return <em>a <strong>boolean array</strong> </em><code>answer</code><em>, where </em><code>answer.length == queries.length</code> <em>and the </em><code>j<sup>th</sup></code> <em>value of </em><code>answer</code> <em>is </em><code>true</code><em> if there is a path for </em><code>queries[j]</code><em> is </em><code>true</code><em>, and </em><code>false</code><em> otherwise</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/08/h.png" style="width: 267px; height: 262px;" />
<pre>
<strong>Input:</strong> n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
<strong>Output:</strong> [false,true]
<strong>Explanation:</strong> The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -&gt; 1 -&gt; 2) of two edges with distances less than 5, thus we return true for this query.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/08/q.png" style="width: 390px; height: 358px;" />
<pre>
<strong>Input:</strong> n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
<strong>Output:</strong> [true,false]
<strong>Explanation:</strong> The above figure shows the given graph.
</pre>

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

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= edgeList.length, queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>edgeList[i].length == 3</code></li>
	<li><code>queries[j].length == 3</code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub>, p<sub>j</sub>, q<sub>j</sub> &lt;= n - 1</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
	<li><code>p<sub>j</sub> != q<sub>j</sub></code></li>
	<li><code>1 &lt;= dis<sub>i</sub>, limit<sub>j</sub> &lt;= 10<sup>9</sup></code></li>
	<li>There may be <strong>multiple</strong> edges between two nodes.</li>
</ul>

class UnionFind:
    def __init__(self,n):
        self.parents = {i:i for i in range(n)}
        self.size = {i:1 for i in range(n)}

    def findParent(self,u):
        if u == self.parents[u]:
            return self.parents[u]
        self.parents[u] = self.findParent(self.parents[u])
        return self.parents[u]

    def union(self,u,v):
        parent_u = self.findParent(u)
        parent_v = self.findParent(v)

        if parent_u == parent_v:
            return 
        if self.size[parent_u] > self.size[parent_v]:
            self.parents[parent_v] = parent_u
            self.size[parent_u] += 1
        else:
            self.parents[parent_u] = parent_v
            self.size[parent_v] += 1
        return
    
    def connected(self,u,v):
        parent_u = self.findParent(u)
        parent_v = self.findParent(v)
        return parent_u == parent_v

class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
        '''Approach: Union Find. The problem asks to check if two nodes can be connected
        with the given limited distance. So the first thing that we need to do is connect
        nodes that can be connected with the current limit. Then check if the two nodes
        are already connected. if they are that means we were able to connect them if
        not the answer to that query would be no. Therefore we sorted both the query and
        the edgelist based on the distance so that we could connect elements with
        smaller distance first. Then we used union find to check whether the two nodes
        belong to the same componenet or not.'''
        #Step1: create a union find class to check if two elements belong to the same component
        union_find = UnionFind(n)
        
        #Step2: append the index on the end of each query so that we know where it was in the final answer
        for index, query in enumerate(queries):
            query.append(index)

        #Step3: sort both the query and the edgelist based on the distance
        queries.sort(key = lambda x : x[2])
        edgeList.sort(key = lambda x : x[2])
        answer = [False for _ in range(len(queries))]
        index = 0

        #Step4: iterate through each query and connect nodes that can be connected with the current limit
        for query in queries:
            u, v, limit = query[:3]
            while index < len(edgeList) and edgeList[index][2] < limit:
                first, second = edgeList[index][:2]
                union_find.union(first,second)
                index += 1

            #check if the two nodes in the query are already connected with the given limit  
            if union_find.connected(u,v):
                answer[query[3]] = True
        
        
        return answer
        #Time Complexity:O(n+m + nlogn) assuming the union find takes amortized O(1) and m is the length of the query
        #Space Complexity: O(2n) for the union find 
1523