<p>There is a <strong>bi-directional</strong> graph with <code>n</code> vertices, where each vertex is labeled from <code>0</code> to <code>n - 1</code> (<strong>inclusive</strong>). The edges in the graph are represented as a 2D integer array <code>edges</code>, where each <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> denotes a bi-directional edge between vertex <code>u<sub>i</sub></code> and vertex <code>v<sub>i</sub></code>. Every vertex pair is connected by <strong>at most one</strong> edge, and no vertex has an edge to itself.</p>

<p>You want to determine if there is a <strong>valid path</strong> that exists from vertex <code>source</code> to vertex <code>destination</code>.</p>

<p>Given <code>edges</code> and the integers <code>n</code>, <code>source</code>, and <code>destination</code>, return <code>true</code><em> if there is a <strong>valid path</strong> from </em><code>source</code><em> to </em><code>destination</code><em>, or </em><code>false</code><em> otherwise</em><em>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png" style="width: 141px; height: 121px;" />
<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
<strong>Output:</strong> true
<strong>Explanation:</strong> There are two paths from vertex 0 to vertex 2:
- 0 &rarr; 1 &rarr; 2
- 0 &rarr; 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png" style="width: 281px; height: 141px;" />
<pre>
<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no path from vertex 0 to vertex 5.
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= edges.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
	<li><code>0 &lt;= source, destination &lt;= n - 1</code></li>
	<li>There are no duplicate edges.</li>
	<li>There are no self edges.</li>
</ul>

"""
Approach 1: Dijkstra's algo to check for distance to destination

1. Get adjacency list
2. Perform Dijkstra's
3. Return true if we were able to visit the destination node

Time: O(V + E*LogV)
V for the visited nodes array
E*LogV for the priority queue
- looping through each adjacencyList edge of a vertex is O(E)
- pop for each edge is O(logE)

Space: O(E + V)
E for adjacency list
V for nodes visited array
"""
"""
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        
        # O(E)
        adjacencyList = collections.defaultdict(list)
        for u,v in edges:
            adjacencyList[u].append(v)
            adjacencyList[v].append(u)
        
        # Dijkstra's
        pq = []

        # O(V)
        visited = [False] * n

        heapq.heappush(pq,source)
        visited[source] = True
        # Overall O(E*LogE) - this is because we're only adding and removing edges once to and from pq
        while pq:
            u = heapq.heappop(pq) # O(logE) note that popping from priority queue of N elements is O(logN)
            
            # Search adjacent connected nodes
            for v in adjacencyList[u]: # O(E) (it's for each edge in that vertex, and worst case, the vertex has all edges)
                if not visited[v]:
                    heapq.heappush(pq,v) #O(LogE) (heappush is log N)
                    visited[v] = True # Do this so we don't append nodes we've seen already
        # Once we're done with searching all connected, nodes, if we visited the dest node
        return visited[destination]
"""



"""
Approach 2: Use set union and union find

1. Use set union to get all sets of connected graphs
2. See if destination is part of the source graph

Time:
O(E + V)
E for iterating through each edge to union the points.
V for find operation, which does path compression. 
  Note that we only do it once per vertex, therefore it's additive instead of multiplicative.
Space:
O(V) 
For storing parents of each vertex.
For the recursive stack if one vertex has a lot of ancestors.
"""
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        
        # Will be used for mapping each vertex to its parent. Initialize parent as themselves for now.
        parent = [i for i in range(n)]

        # Find looks for the root-ancestor node. 
        # It also does path compression (setting the parents of this node and ancestor nodes to be the root-ancestor node) 
        # to make future calls to find() for this set be O(1).
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        # Puts y's root-ancestor to be under x's root-ancestor. 
        # This means x and y are now in the same set.
        def union(x,y):
            parent[find(y)] = find(x)

        # Iterate through each edge and join any vertices that are paired together
        for u,v in edges: # O(E)
            if find(u) != find(v): # O(1). This can be O(V), but will just be a sum instead of multiplying
                union(u,v) # O(1). This can be O(V), but will just be a sum instead of multiplying 
        
        # Check if destination is reachable from the source node by seeing if they have the same parent
        return find(source) == find(destination) # O(1). This can be O(V), but will just be a sum instead of multiplying 
73342