class DisjointSetForest::DisjointSetForest

Public Class Methods

new() click to toggle source
# File lib/disjoint_set_forest/disjoint_set_forest.rb, line 4
def initialize
  @parent = {}
  @rank = {}
end

Public Instance Methods

find(x) click to toggle source
# File lib/disjoint_set_forest/disjoint_set_forest.rb, line 14
def find(x)
  if @parent[x] != x
    @parent[x] = self.find(@parent[x])
  end
  @parent[x]
end
make_set(x) click to toggle source
# File lib/disjoint_set_forest/disjoint_set_forest.rb, line 9
def make_set(x)
  @parent[x] = x
  @rank[x] = 0
end
union(x, y) click to toggle source
# File lib/disjoint_set_forest/disjoint_set_forest.rb, line 21
def union(x, y)

  x_root = self.find(x)
  y_root = self.find(y)

  return if x_root == y_root

  if @rank[x_root] == @rank[y_root]
    @parent[y_root] = @parent[x_root]
    @rank[x_root] += 1
  elsif @rank[x_root] > @rank[y_root]
    @parent[y_root] = @parent[x_root]
  else
    @parent[x_root] = @parent[y_root]
    @rank[y_root] += 1
  end

end