< Back





1971. Find if Path Exists in Graph

We're given an undirected graph with a source and destination node. We're asked to determine if
there exists a path between the two nodes in the graph. This is a classic connectivity problem, we
can solve this by using Union-Find. For each edge, (x, y), we know each node is connected, so we
execute union_set on the two nodes to reflect that. After processing all the edges, the Union-Find
data structure will have all the nodes connected in their disjoint sets. If two nodes are both in
the same disjoint set, then a path exists between. Therefore, if our source and destination nodes
are in the same set, we return True - there is a path between them. Otherwise, we return False.

The solution is as follows:


  from collections import defaultdict

  class UnionFind:
      def __init__(self, n: int) -> None:
          self.parent, self.rank = [i for i in range(n)], [0 for _ in range(n)]

      def find(self, x: int) -> int:
          if self.parent[x] != x:
              self.parent[x] = self.find(self.parent[x])
          return self.parent[x]

      def union_set(self, x: int, y: int) -> None:
          xset, yset = self.find(x), self.find(y)

          if xset != yset:
              if self.rank[xset] < self.rank[yset]:
                  self.parent[xset] = yset
              elif self.rank[yset] < self.rank[xset]:
                  self.parent[yset] = xset
              else:
                  self.parent[yset] = xset
                  self.rank[xset] += 1

  class Solution:
      def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
          uf = UnionFind(n)

          for x, y in edges:
              uf.union_set(x, y)

          return uf.find(source) == uf.find(destination)


_ Time Complexity:

  O(m) - We iterate through the edges to perform union_set.

_ Space Complexity:

  O(n) - We track the parents and ranks of each node.