Sha256: 958df3a7be6d93a58bce9a30cb4d3927a50f4b004fd32940043c58cd2263712c

Contents?: true

Size: 732 Bytes

Versions: 5

Compression:

Stored size: 732 Bytes

Contents

require_relative './scc.rb'

# TwoSAT
# Reference: https://github.com/atcoder/ac-library/blob/master/atcoder/twosat.hpp
class TwoSAT
  def initialize(n = 0)
    @n = n
    @answer = Array.new(n)
    @scc = SCCGraph.new(2 * n)
  end

  attr_reader :answer

  def add_clause(i, f, j, g)
    raise RangeError unless (0...@n).cover?(i) && (0...@n).cover?(j)

    @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

  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
  alias satisfiable? satisfiable
end

TwoSat = TwoSAT

Version data entries

5 entries across 5 versions & 1 rubygems

Version Path
ac-library-rb-0.5.4 lib/two_sat.rb
ac-library-rb-0.5.3 lib/two_sat.rb
ac-library-rb-0.5.2 lib/two_sat.rb
ac-library-rb-0.5.1 lib/two_sat.rb
ac-library-rb-0.5.0 lib/two_sat.rb