Find if Path Exists in Graph — BFS/Union-Find

Problem

Given n nodes and edges in an undirected graph, return true if there's a valid path from source to destination.

Solutions

Python — BFS

from collections import deque, defaultdict
class Solution:
    def validPath(self, n, edges, source, destination):
        if source==destination: return True
        adj=defaultdict(list)
        for u,v in edges: adj[u].append(v); adj[v].append(u)
        visited={source}; q=deque([source])
        while q:
            node=q.popleft()
            for nb in adj[node]:
                if nb==destination: return True
                if nb not in visited: visited.add(nb); q.append(nb)
        return False

Python — Union-Find

class Solution:
    def validPath(self, n, edges, source, destination):
        parent=list(range(n))
        def find(x):
            while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
            return x
        for u,v in edges:
            pu,pv=find(u),find(v)
            if pu!=pv: parent[pu]=pv
        return find(source)==find(destination)

Complexity

Time: O(V+E) | Space: O(V+E)