class 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