2-SAT 学习笔记


给你 \(n\) 个随机变量,每个随机变量有两个取值。

把变量 \(i\) 拆成 \(i_1,i_2\)

\(u \rightarrow v\) 表示选 \(u\) 必须选 \(v\)

可行性就是缩点之后判每个随机变量的两个点是否在一个强连通分量内。

方案优先选缩点之后拓扑序大的。

注意条件要建全,“对称性”。

相关