class AcLibraryRb::TwoSAT

TwoSAT Reference: github.com/atcoder/ac-library/blob/master/atcoder/twosat.hpp

Attributes

answer[R]

Public Class Methods

new(n) click to toggle source
# File lib_lock/ac-library-rb/two_sat.rb, line 7
def initialize(n)
  @n = n
  @answer = Array.new(n)
  @scc = SCC.new(2 * n)
end

Public Instance Methods

add_clause(i, f, j, g) click to toggle source
# File lib_lock/ac-library-rb/two_sat.rb, line 15
def add_clause(i, f, j, g)
  unless 0 <= i && i < @n and 0 <= j && j < @n
    raise ArgumentError.new("i:#{i} and j:#{j} must be in (0...#{@n})")
  end

  @scc.add_edge(2 * i + (f ? 0 : 1), 2 * j + (g ? 1 : 0))
  @scc.add_edge(2 * j + (g ? 0 : 1), 2 * i + (f ? 1 : 0))
  nil
end
satisfiable()
Alias for: satisfiable?
satisfiable?() click to toggle source
# File lib_lock/ac-library-rb/two_sat.rb, line 25
def satisfiable?
  id = @scc.send(:scc_ids)[1]
  @n.times do |i|
    return false if id[2 * i] == id[2 * i + 1]

    @answer[i] = id[2 * i] < id[2 * i + 1]
  end
  true
end
Also aliased as: satisfiable