今回のお題はこちら。
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