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

from collections import Counter,deque
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if destination>n-1:
            return False

        def dfs_helper(G,source,destination,visited): #using bfs
            if source==destination: #base case
                return True 

            visited[source]=1 #visited now
            for adj_node in G[source]: # for all the neighbours
                if not visited[adj_node]: # if not visited then only perform DFS
                    if dfs_helper(G,adj_node,destination,visited): # if u find a destination in the dfs of other node then return True
                        return True

            return False #else return False

        def bfs_helper(G,source,destination,visited): #using bfs
            visited[source]=1
            step=1
            level,parent={},{}
            parent[source]=-1
            level[source]=step-1
            queue=deque()
            queue.append(source)
            while queue:
                que_size=len(queue)
                for _ in range(len(queue)):
                    node=queue.popleft() #pop the first node and process
                    if node==destination: #path found 
                        return True
                    for neigh in G[node]:  # for all the neighbours 
                        if not visited[neigh]: #process only if not visited
                            visited[neigh]=1 # make visited to 1
                            queue.append(neigh) # append it to queue for futher processing
                            level[neigh]=step # level
                            parent[neigh]=node # parent will be the current node

                step+=1 #step increment

        
        G=defaultdict(list)
        visited=[0]*(n) #keep track of visitwed or not - inititalise with zero as the process yet to start
        #create adjacency list
        for edge in edges:
            G[edge[0]].append(edge[1])
            G[edge[1]].append(edge[0]) #remove incase of unidirectional

        # if dfs_helper(G,source,destination,visited):
        #     return True
        # return False    

        if bfs_helper(G,source,destination,visited):
            return True
        return False    

        
        


123957