今日解いた問題2

アルゴリズム Ruby

彩色問題

アリ本の93ページ
隣接したりノードが同じ色にならないように色をぬる。
今回は２色で塗ることができるかという問題
特に２色でぬれるグラフを２部グラフという

コードで言うと0が塗ってないノードなので下の２つを繰り返す感じ

  • 隣接したノードjが0ならノードjに対して色(-c)を塗る
  • 隣接したノードjと現在のノードがiが同じ色c(1 or 0)ならfalseを返す
G1 = [[0, 1, 1],
      [1, 0, 1],
      [1, 1, 0]].freeze

G2 = [[0, 1, 0, 1],
      [1, 0, 1, 0],
      [0, 1, 0, 1],
      [1, 0, 1, 0]].freeze

s = G2.size
$color = Array.new(s, 0)         # 0は塗ってない 1と-1が塗った

def dfs(i, c)
  $color[i] = c

  G2[i].each_with_index do |e, j|
    next unless e == 1
    return false if $color[j] == c
    return false if $color[j].zero? && !dfs(j, -c)
  end

  true
end

s.times do |i|
  next unless $color[i].zero?
  unless dfs(i, 1)
    puts 'NO'
    break
  end
  puts 'YES'
end