プログラミングコンテストチャレンジブック演習「食物連鎖」

今回のお題はこちら。

union find treeも一緒に実装しました。
このデータ構造初めて知ったなぁ。

class UnionFindTree
  attr_accessor :parent, :rank
  
  def initialize(n)
    @parent = Array.new
    @rank = Array.new
    for i in 0..(n - 1)
      @parent.push(i)
      rank.push(0)
    end
  end

  def find(x)
    if @parent[x] == x
      return x
    else
      return @parent[x] = find(@parent[x])
    end
  end

  def unite(x, y)
    root_x = find(x)
    root_y = find(y)
    return if root_x == root_y

    if rank[x] < rank[y]
      @parent[x] = y
    else
      @parent[y] = x
    end

    rank[x] += 1 if rank[x] == rank[y]
  end

  def is_same(x, y)
    return find(x) == find(y)
  end
end

require 'union_find_tree'

MaxN = 100
MaxK = 7

class Input
  attr_accessor :type, :x, :y, :no
  def initialize(type, x, y, no)
    @type = type
    @x = x
    @y = y
    @no = no
  end
end

inputs = Array.new #input
inputs.push(Input.new(1, 101, 1, 1))
inputs.push(Input.new(2, 1, 2, 2))
inputs.push(Input.new(2, 2, 3, 3))
inputs.push(Input.new(2, 3, 3, 4))
inputs.push(Input.new(1, 1, 3, 5))
inputs.push(Input.new(2, 3, 1, 6))
inputs.push(Input.new(1, 5, 5, 7))

u = UnionFindTree.new(MaxN * 3)

answer = 0
inputs.each do |input|
  x = input.x
  y = input.y
  if x < 0 || x > MaxN || y < 0 || y > MaxN
    answer += 1
    next
  end

  if input.x == 1
    if u.is_same(x, y + MaxN) || u.is_same(x, y + MaxN * 2)
      answer += 1
    else
      u.unite(x, y)
      u.unite(x + MaxN, y + MaxN)
      u.unite(x + MaxN * 2, y + MaxN * 2)
    end
  else
    if u.is_same(x, y) || u.is_same(x, y + MaxN * 2)
      answer += 1
    else
      u.unite(x, y + MaxN)
      u.unite(x + MaxN, y + MaxN * 2)
      u.unite(x + MaxN * 2, y)
    end
  end
end

puts answer