<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>

class Solution:
       # finding if a path exists
    # n vertices, 0 to n-1 (inclusive)
    # edges[i] = [ui, vi] edge between node ui and node vi 
    # ui to ui edge. any pair of vertices has atmost one edge.
    # determine a valid path from source to destination
    def __init__(self):
        self.set_of_visited_vertices : Set = set()

    # BFS - source 0 and destination 5. 
    from typing import List, Set, Deque, Dict
    from collections import deque, OrderedDict

    

    def bfs(self,adjacency_list: Dict[int, List[int]], source : int, destination : int) -> bool:
        if source == destination:
            return True
        if not adjacency_list:
            return False

        set_of_visited_vertices = set()
        set_of_visited_vertices.add(source)
        queue : Deque = deque()
        level = 0
        queue.append((source, level))
        is_found = False

        while bool(queue):
            curr_vertex, curr_level = queue.popleft()
            if destination in adjacency_list[curr_vertex]:
                is_found = True
                break
            for n_vertex in adjacency_list[curr_vertex]:
                if n_vertex not in set_of_visited_vertices:
                    set_of_visited_vertices.add(n_vertex)
                    queue.append( (n_vertex, curr_level+1) )

        return is_found

    def dfs_iterative(self, adjacency_list: Dict[int, List[int]], source : int, destination : int) -> bool:
        
        stack : Deque = deque()
        stack.append(source)
        self.set_of_visited_vertices.add(source)
        is_found: bool = False
            
    
        while bool(stack):
            curr_vertex = stack.pop()
            if curr_vertex == destination:
                is_found = True
                break        
            
            # check if destination is in the vertex
            if destination in adjacency_list[curr_vertex]:
                is_found = True
                break

            for n_vertex in adjacency_list[curr_vertex]:
                if n_vertex not in self.set_of_visited_vertices:
                    self.set_of_visited_vertices.add(n_vertex)
                    stack.append(n_vertex)

        return is_found
    
    def convert_edges_to_adjacency_list(self,edges : List[List[int]]) -> Dict[int,List[int]]:
        adjacency_list : OrderedDict[int, List[int]] = OrderedDict()
        for vertex1, vertex2 in edges:
            if vertex1 not in adjacency_list:
                adjacency_list[vertex1] = [vertex2]
            else:
                adjacency_list[vertex1].append(vertex2)
            if vertex2 not in adjacency_list:
                adjacency_list[vertex2] = [vertex1]
            else:
                adjacency_list[vertex2].append(vertex1)
        return adjacency_list 

    def validPath(self,n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        assert (0 <= source <= n-1 and 0 <= destination <= n-1)
        adjacency_list = self.convert_edges_to_adjacency_list(edges = edges)
        self.set_of_visited_vertices.add(source)
        #return self.dfs_iterative(adjacency_list, source, destination)
        return self.bfs(adjacency_list, source, destination)

#    def test_case_1():
#        edges = [[0,1],[1,2],[2,0]]
#        source = 0
#        destination = 2
#        n = 3
#        assert(validPath(3,edges,source, destination) == True)
#
#    def test_case_2():
#        edges = [[0,1],[0,2],[3,5],[5,4],[4,3]]
#        source = 1
#        destination = 5
#        n = 6
#        assert(validPath(3,edges,source, destination) == False)
#
113452