Logo

Programming-Idioms

# 187 Disjoint Set
New implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating resource.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations
public class DisjointSetElement {
  private DisjointSetElement representative = this;

  public DisjointSetElement getRepresentative() {
    if (representative != this) {
      representative = representative.getRepresentative();
    }
    return representative;
  }

  public void union(DisjointSetElement other) {
    other.getRepresentative().representative = getRepresentative();
  }
}
  
class UnionFind:
    def __init__(self, size):
        self.rank = [0] * size
        self.p = [i for i in range(size)]

    def find_set(self, i):
        if self.p[i] == i:
            return i
        else:
            self.p[i] = self.find_set(self.p[i])
            return self.p[i]

    def is_same_set(self, i, j):
        return self.find_set(i) == self.find_set(j)

    def union_set(self, i, j):
        if not self.is_same_set(i, j):
            x, y = self.find_set(i), self.find_set(j)
 
require 'set'
a.disjoint?(b)