src/datastructure/union_find.cr

• View this file on GitHub
• Last update: 2022-04-16 07:49:21+00:00

Required by

• src/graph/components.cr
• src/graph/decompose.cr
• src/graph/kruskal.cr
• test/graph/namori_decompose_test_.cr

Verified with

• test/datastructure/union_find_test.cr
• test/graph/components_test.cr
• test/graph/compress_degree_test.cr
• test/graph/decompose_test.cr
• test/graph/kruskal_test.cr

Code

class UnionFind
  @d : Array(Int32)
  getter count_components : Int32

  def initialize(n : Int)
    @d = Array.new(n, -1)
    @count_components = n
  end

  def initialize(n : Int, edges : Enumerable({Int32, Int32}))
    initialize(n)
    edges.each { |u, v| unite(u, v) }
  end

  def root(x : Int)
    @d[x] < 0 ? x : (@d[x] = root(@d[x]))
  end

  def unite(x : Int, y : Int)
    x = root(x)
    y = root(y)
    return false if x == y
    x, y = y, x if @d[x] > @d[y]
    @d[x] += @d[y]
    @d[y] = x
    @count_components -= 1
    true
  end

  def same?(x : Int, y : Int)
    root(x) == root(y)
  end

  def size(x : Int)
    -@d[root(x)]
  end

  def groups
    groups = Hash(Int32, Set(Int32)).new { |h, k| h[k] = Set(Int32).new }
    @d.size.times do |i|
      groups[root(i)] << i
    end
    groups.values.to_set
  end
end

class UnionFind
  @d : Array(Int32)
  getter count_components : Int32

  def initialize(n : Int)
    @d = Array.new(n, -1)
    @count_components = n
  end

  def initialize(n : Int, edges : Enumerable({Int32, Int32}))
    initialize(n)
    edges.each { |u, v| unite(u, v) }
  end

  def root(x : Int)
    @d[x] < 0 ? x : (@d[x] = root(@d[x]))
  end

  def unite(x : Int, y : Int)
    x = root(x)
    y = root(y)
    return false if x == y
    x, y = y, x if @d[x] > @d[y]
    @d[x] += @d[y]
    @d[y] = x
    @count_components -= 1
    true
  end

  def same?(x : Int, y : Int)
    root(x) == root(y)
  end

  def size(x : Int)
    -@d[root(x)]
  end

  def groups
    groups = Hash(Int32, Set(Int32)).new { |h, k| h[k] = Set(Int32).new }
    @d.size.times do |i|
      groups[root(i)] << i
    end
    groups.values.to_set
  end
end

Back to top page