ruby - 如何找出我的逻辑缺陷？

Question

我很难找出我的逻辑缺陷。

3是 的父级4并且8是 的父级3。我想9指出它的根4是8.

这是我的 Ruby 课程：

class QuickUnion

  def initialize(n)
    @id = Array.new(n) {|i| i}
  end

  def root(i)
    while i != @id[i] do
      i = @id[i]
    end
    i
  end

  def connected?(p, q)
    root(p) == root(q)
  end

  def union(p, q)
     @id[p] = @id[q]
  end

  def print_union
    puts "#{@id}"
  end

end

这是测试文件：

qu = QuickUnion.new(10)
qu.print_union
qu.union(4,3)
qu.print_union
qu.union(3,8)
qu.print_union
qu.union(6,5)
qu.print_union
qu.union(9,4)
qu.print_union

这是输出：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 3, 5, 6, 7, 8, 9]
[0, 1, 2, 8, 3, 5, 6, 7, 8, 9]
[0, 1, 2, 8, 3, 5, 5, 7, 8, 9]
[0, 1, 2, 8, 3, 5, 5, 7, 8, 3]

最后一个数组的输出应该是：

[0, 1, 2, 8, 3, 5, 5, 7, 8, 8]

任何帮助表示赞赏。

Answer 1

union(9,4)正在分配@id[9] = @id[4] = 3。

在 ruby​​ 中，数组的索引从 0 开始，而不是 1。

Answer 2

用以下内容替换您的联合方法：

def union(p, q)
     @id[p] = root(@id[q])
end

有很多方法可以实现这一点，我发现这是最简单的（因为辅助函数已经到位）