2-SAT的定义

\(2-SAT\)是对于一类限制问题类似于\(a_1 or a_2 = 0\)之类的每个限制只有两个元素，求解一个合法的全体序列问题。

解法

发现此类条件具有指向性。
拆点。
连\(u\to v\),表示若\(u\)成立则\(v\)一定成立

若\(u\)可以推出\(v\)则\(u\)非法，\(v\)合法。

有向无环图中，合法点的拓扑序比非法点大

强连通分量中，任意点合法则全体点合法。

可以发现强连通分量的编号实际上和拓扑序相关

同一元素拆点后强连通分量编号小的点是合法点
若两点在一起则无解。