two_sat
クラス · 2-SAT
struct two_sat;
概要
2-SAT
計算量
- 変数数を $V$、節数を $C$ として構築 $O(V)$、求解 $O(V+C)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
n変数の2-SATを構築する | $O(V)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
add |
節(iがf) OR (jがg)を追加する | 償却 $O(1)$ |
solve |
含意グラフの強連結成分番号を返す | $O(V+C)$ |
is_satisfy |
solveが返した成分番号が充足可能か確認する | $O(V)$ |
build |
成分番号から各変数の真偽値を構築する | $O(V)$ |