プログラミングコンテストチャレンジブック演習「二部グラフ判定」

今回のお題はこちら。

DFSにも大分なれてきました。

$graph = Array.new(4).map!{ Array.new() }
$graph[0].push(1)
$graph[0].push(3)
$graph[1].push(0)
$graph[1].push(2)
$graph[2].push(1)
$graph[2].push(3)
$graph[3].push(0)
$graph[3].push(2)

$color = Array.new(4, 0)

def dfs(v, c)
  $color[v] = c
  $graph[v].each do |ve|
    return false if $color[ve] == $color[v]
    return dfs(ve, -c) if $color[ve] == 0
  end

  return true
end

$graph.each_with_index do |g, i|
  if $color[i] == 0
    if !dfs(i, 1)
      puts "No"
      return
    end
  end
end

puts "Yes"