1class QuickUnion
 2  def initialize(size)
 3    @items = Array.new(size) { |n| n }
 4    @size = Array.new(size, 0)
 5  end
 6
 7  def union(x, y)
 8    i = root_of(x)
 9    j = root_of(y)
10    return if (i == j)
11
12    if @size[i] < @size[j]
13      @items[i] = j
14      @size[j] = @size[j] + @size[i]
15    else
16      @items[j] = i
17      @size[i] = @size[i] + @size[j]
18    end
19  end
20
21  def connected?(x, y)
22    root_of(x) == root_of(y)
23  end
24
25  private
26
27  def root_of(x)
28    x = @items[x] until @items[x] == x
29    x
30  end
31end