< Back




547. Number of Provinces

We're asked to determine the connectivity of a graph of cities, and return the number of provinces.
We're essentially being asked to return the number of connected components in the graph. To do this
in the fastest and coolest way possible, we can use Union-Find. The normal way to solve this is
depth-first search - but Union-Find is way cooler.

Union-Find is a data structure that keeps track of elements which are split into one or more
disjoint sets. For each node, we check to see if they're connected. If they are, we check to see if
they're in the same disjoint set. If not, we merge the sets and decrease our count of connected
components.

The solution is as follows:


  class UnionFind:
      def __init__(self, n: int) -> None:
          self.parent = [i for i in range(n)]
          self.rank = [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:
              return
          elif 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 findCircleNum(self, isConnected: List[List[int]]) -> int:
          n = len(isConnected)
          dsu = UnionFind(n)
          ans = n

          for i in range(n):
              for j in range(i + 1, n):
                  if isConnected[i][j] and dsu.find(i) != dsu.find(j):
                      ans -= 1
                      dsu.union_set(i, j)

          return ans


_ Time Complexity:

  O(n^2) - We iterate over all values in isConnected.

_ Space Complexity:

  O(n) - We maintain the parent and rank arrays.