Disjoint Set Union

Definition:

• Naive :

  void make_set(int v) {
      parent[v] = v;
  }
   
  int find_set(int v) {
      if (v == parent[v])
          return v;
      return find_set(parent[v]);
  }
   
  void union_sets(int a, int b) {
      a = find_set(a);
      b = find_set(b);
      if (a != b)
          parent[b] = a;
  }

Optimizations: 

• Path Compression: point all the nodes to 1 most root

  int find_set(int v) {
      if (v == parent[v])
          return v;
      return parent[v] = find_set(parent[v]);
  }

• Union by Rank/Size:
  • rank

  class DSU:
      def __init__(self, n):
          self.parent = list(range(n + 1))
          self.rank = [0] * (n + 1)
      def find(self, x):
          if self.parent[x] != x:
              self.parent[x] = self.find(self.parent[x])
          return self.parent[x]
      def union(self, x, y):
          xr, yr = self.find(x), self.find(y)
          if xr == yr:
              return
          if self.rank[xr] < self.rank[yr]:
              self.parent[xr] = yr
          elif self.rank[xr] > self.rank[yr]:
              self.parent[yr] = xr
          else:
              self.parent[yr] = xr
              self.rank[xr] += 1
   

Applications: 

• Kruskal’s MST, Connected Components in a graph, and Cycle Detection in undirected graphs.