2-SAT Solver

keyword:

カートに追加

overview

2-SATを解く. 強連結成分分解は内包済み.DGraphが必要.

usage

Sat_2(size_t n)
; 
void Sat_2::emplace(int a, int b)
; 節を追加する.節は2つのリテラルから構成される.
; リテラルの番号は1-indexed.
; 負のインデックスを指定すると,否定として扱われる.
bool Sat_2::solve(vector& result)
@ret : 充足可能かどうか
; result[i]は,i番目のリテラルがTかFか.
; result[0]はdontcare

verified

http://yukicoder.me/submissions/142141

references

http://www.prefield.com/algorithm/misc/2-sat.html

require

code