class DisjointSet::DisjointSet

DisjointSet

Attributes

parent[R]
rank[R]

Public Class Methods

new(ids = []) click to toggle source
# File lib/disjoint_set/disjoint_set.rb, line 6
def initialize(ids = [])
  @parent, @rank = {}, {}
  ids.each do |id|
    @parent[id] = id
    @rank[id] = 0
  end
end

Public Instance Methods

find(x) click to toggle source
# File lib/disjoint_set/disjoint_set.rb, line 19
def find(x)
  return x if (@parent[x] == x)
  @parent[x] = find(@parent[x])
  @parent[x]
end
make_set(x) click to toggle source
# File lib/disjoint_set/disjoint_set.rb, line 14
def make_set(x)
  @parent[x] = x
  @rank[x] = 0
end
same?(x, y) click to toggle source
# File lib/disjoint_set/disjoint_set.rb, line 41
def same?(x, y)
  find(x) == find(y)
end
union(x, y) click to toggle source
# File lib/disjoint_set/disjoint_set.rb, line 25
def union(x, y)
  x, y, rank_x, rank_y =
    find(x), find(y), @rank[x], @rank[y]

  return if (x == y)

  if (rank_x > rank_y)
    @parent[y] = x
  elsif (rank_x < rank_y)
    @parent[x] = y
  else
    @parent[y] = x
    @rank[x] += 1
  end
end