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?()
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