< Back





323. Number of Connected Components in an Undirected Graph

Regular graph connectivity question. We use UnionFind on all the edges to find the number of
connected components. Each time we merge two nodes, we decrement the number of connected components.

The solution is as follows:


  class UnionFind:
      def __init__(self, n: int) -> None:
          self.count = n
          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

              self.count -= 1

      def get_count(self) -> int:
          return self.count

  class Solution:
      def countComponents(self, n: int, edges: List[List[int]]) -> int:
          uf = UnionFind(n)

          for u, v in edges:
              uf.union_set(u, v)

          return uf.get_count()


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