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