LC1971. Find if Path Exists in Graph

Approach 1: DFS

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        # 1. Build adjacency list
        adj = defaultdict(set)
        for s, d in edges:
            adj[s].add(d)
            adj[d].add(s)
 
        seen = set()
        def dfs(dest):
            if dest == destination:
                return True
            
            seen.add(dest)
            
            for node in adj[dest]:
                if node not in seen and dfs(node):
                    return True
            
            return False
        
        return dfs(source)

Complexity

Time: $O(n+m)$ where $n$ is number of nodes in graph and $m$ is number of edges.
Space: O(n + m)$

Approach 2: BFS

Complexity

Time:
Space:

Notes

TODO