Leetcode # 323. Number of Connected Components in an Undirected Graph

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph

Solution: Disjoint Set Union (DSU)

Time Complexity: O()
Space Complexity: O()
(The input and output generally do not count towards the space complexity.)

class Dsu:
  def __init__(self, roots = None):
    self.root = {}
    self.rank = {}
    if roots:
      for r in roots:
        self.make_set(r)

  def make_set(self, x): 
    self.root[x] = x
    self.rank[x] = 0

  def find(self, x):
    if self.root[x] == x:
      return x
    self.root[x] = self.find(self.root[x])
    return self.root[x]

  def union(self, x, y): 
    x_root = self.find(x) 
    y_root = self.find(y) 
    if x_root != y_root: 
      if self.rank[x_root] < self.rank[y_root]:
        large = y_root
        small = x_root 
      else:
        large = x_root 
        small = y_root
    
      self.root[small] = large
      if self.rank[large] == self.rank[small]:
        self.rank[large] += 1

  def get_ds(self):
    disjoint_sets = collections.defaultdict(set)
    for key in self.root:
      disjoint_sets[self.find(key)].add(key)
    return disjoint_sets

class Solution:
  def countComponents(self, n: int, edges: List[List[int]]) -> int:
    dsu = Dsu([i for i in range(n)])
    for edge in edges:
      dsu.union(*edge)
    dsu.get_ds()
    
    print(dsu.get_ds())
    return len(dsu.get_ds())

Last Updated on 2023/08/16 by A1go