二部グラフの問題ぜんぶ解く

と言っても探したけど3つしかなくて、しかもコードがどれも同じになってしまって、ぜんぶ解く意味があまりなかった。

[math-and-algorithm 047] Bipartite Graph

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ao

N, M = gets.split.collect(&:to_i)
AB = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 5], [1, 6], [2, 7], [3, 7], [4, 6], [5, 8], [6, 8]]

@edges = {}
AB.each do |a, b|
  @edges[a] ||= []
  @edges[a] << b
  @edges[b] ||= []
  @edges[b] << a
end
@edges                                               # => {1=>[5, 6], 5=>[1, 8], 6=>[1, 4, 8], 2=>[7], 7=>[2, 3], 3=>[7], 4=>[6], 8=>[5, 6]}

# どの問題も、ここからのコードぜんぶ同じ！

@visited = {}

def dfs(from, color)
  @visited[from] = color
  @edges[from].each do |to|
    if @visited[to] == color
      return false
    end
    if !@visited[to] && !dfs(to, color ^ 1)
      return false
    end
  end
  true
end

bipartite = true
@edges.each_key do |from|
  if @visited[from]
    next
  end
  unless dfs(from, 0)
    bipartite = false
    break
  end
end

puts bipartite ? "Yes" : "No"
__END__
8 7
1 5
1 6
2 7
3 7
4 6
5 8
6 8

[ABC282 D] Make Bipartite 2

https://atcoder.jp/contests/abc282/tasks/abc282_d

コード

N, M = gets.split.collect(&:to_i)
AB = M.times.collect { gets.split.collect(&:to_i) }  # => [[4, 2], [3, 1], [5, 2], [3, 2]]

@edges = {}
AB.each do |a, b|
  @edges[a] ||= []
  @edges[a] << b
  @edges[b] ||= []
  @edges[b] << a
end
@edges                                               # => {4=>[2], 2=>[4, 5, 3], 3=>[1, 2], 1=>[3], 5=>[2]}

# どの問題も、ここからのコードぜんぶ同じ！

@visited = {}

def dfs(from, color)
  @visited[from] = color
  @edges[from].each do |to|
    if @visited[to] == color
      return false
    end
    if !@visited[to] && !dfs(to, color ^ 1)
      return false
    end
  end
  true
end

bipartite = true
@edges.each_key do |from|
  if @visited[from]
    next
  end
  unless dfs(from, 0)
    bipartite = false
    break
  end
end

puts bipartite ? "Yes" : "No"
__END__
5 4
4 2
3 1
5 2
3 2

1問目とコードが完全に同じ。こちらも二部グラフの問題だと問題文に書いてくれている。

[ABC327 D] Good Tuple Problem

https://atcoder.jp/contests/abc327/tasks/abc327_d

コード

N, M = gets.split.collect(&:to_i)
A = gets.split.collect(&:to_i).collect(&:pred)  # => [0, 1, 2]
B = gets.split.collect(&:to_i).collect(&:pred)  # => [1, 2, 0]

@edges = {}
M.times do |i|
  @edges[A[i]] ||= []
  @edges[A[i]] << B[i]
  @edges[B[i]] ||= []
  @edges[B[i]] << A[i]
end
@edges                                          # => {0=>[1, 2], 1=>[0, 2], 2=>[1, 0]}

# どの問題も、ここからのコードぜんぶ同じ！

@visited = {}

def dfs(from, color)
  @visited[from] = color
  @edges[from].each do |to|
    if @visited[to] == color
      return false
    end
    if !@visited[to] && !dfs(to, color ^ 1)
      return false
    end
  end
  true
end

bipartite = true
@edges.each_key do |from|
  if @visited[from]
    next
  end
  unless dfs(from, 0)
    bipartite = false
    break
  end
end

puts bipartite ? "Yes" : "No"
__END__
3 3
1 2 3
2 3 1

入力が横並びで来ただけの違い。ただ、二部グラフ問題だとは問題文のどこにも書かれていない。

参照

https://prd-xxx.hateblo.jp/entry/2017/10/13/004256