<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:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        """
        thought：
        - the description define a `REAL GRAPH` with some definitions：
            - bi-directional, which means it's a UNDIRECTED graph
            - every vertex pair is connected by at most one edge, which means it's a REAL graph
                # no duplicate edges
                # no self edges
        - our goal is to determine whether there's a valid path that exists from vertex `source` to vertex `destination`
            - Note that length of `edges` may be ZERO
        - we can use `BFS` or `DFS` algorithms to check through the GRAPH
        - therefore, we can follow these steps：
            (1) check if length of edges is ZERO
            (2) store vertex in `adjacency list`
                # use `adjacency list` instead of `adjacency matrix` because the former can be traversed through faster
            -------------------
            [ BFS version - queue x loop ]
            (3) use `queue` data structure (FIFO) to store the vertex in order
            (4) use `loop` to traverse through graph and get the route from `source` to the end
            [ DFS version - stack x loop ]
            (3) use `stack` data structure (LIFO) to store the vertex in order
            (4) use `loop` to traverse through graph and get the route from `source` to the end
            -------------------
            (5) check whether destination in route or not and return boolean value
        """
        # check length
        if edges == []:
            if source == destination:
                return True
            else:
                return False
        # adjacency list store graph
        adjacency_list = {}
        for edge in edges:
            vertex1, vertex2 = edge[0], edge[1]
            if vertex1 in adjacency_list:
                adjacency_list[vertex1].append(vertex2)
            else:
                adjacency_list[vertex1] = [vertex2]
            if vertex2 in adjacency_list:
                adjacency_list[vertex2].append(vertex1)
            else:
                adjacency_list[vertex2] = [vertex1]
        # # BFS
        # queue = [source]
        # visited = {source:True} # to record those vertex already visited
        # route = []
        # while len(queue) > 0:
        #     current = queue.pop(0)
        #     route.append(current)
        #     for neighbor in adjacency_list[current]:
        #         if neighbor not in visited:
        #             queue.append(neighbor)
        #             visited[neighbor] = True
        # DFS
        stack = [source]
        visited = {source:True} # to record those vertex already visited
        route = []
        while len(stack) > 0:
            current = stack.pop()
            route.append(current)
            for neighbor in adjacency_list[current]:
                if neighbor not in visited:
                    stack.append(neighbor)
                    visited[neighbor] = True
        # check whether destination in route or not and return boolean value 
        if destination in route:
            return True
        else:
            return False
111542