2-sat

SAT的全称是Satisfiability。

Satisfiability，可满足性。

SAT问题就是要确定一个满足所有条件的方案或判断某方案是否合理。

举个栗子：

有$N$个国家，每个国家有$M$名代表，其中一些国家的一些代表有冲突。

现在这$N$个国家要召开会议，每个国家要派一名代表，且被派出的代表两两间没有冲突，求一个可行的方案。

这就是一个典型的SAT问题。

国家相当于条件，不同的代表相当于不同的情况。

上述的就是M-SAT问题，因为每个条件有M种情况。

同理，当每个条件都只有两种情况时，就是2-SAT问题。

为什么只研究2-SAT而不研究M更大的SAT问题呢？

因为当$M\ge3$时，这是NP完全问题。

很简单，将有必选关系的点连边，然后随便选一个条件的一个情况跑一遍看有没有冲突，有的话就换一个情况跑。

讲得太简单了？

那我再详细点：

还是像上面的那个问题，但规定$M$为$2$（不是2就不是2-SAT问题）。

若$A$国的代表$A_1$与$B$国的代表$B_1$有冲突，那么就可以知道，如果国派的是代表$A_1$，那国能且只能派代表$B_2$，所以就在代表$A_1B_2$间连一条有向边，从$A_1$指向$B_2$，表示选$A_1$就必选$B_2$。同理，选$B_1$必选$A_2$，这就是必选关系。

连好边之后就枚举每个还没确定代表（情况）国家（条件）。对于当前国家（条件），先随便选一个代表（情况），然后沿必选关系往下走，如果发现有冲突（访问到某个国家，发现其另一个代表也是必选的），就返回，换另一个代表试。如果两个代表都不行，就说明不存在合法情况。

这时你可能要问了，为什么是换当前国家的代表，不换之前选过的？

其实不难看出，这个图是对称的，所以出现冲突时换哪个国家的代表都无所谓（实在还不懂的，可以自己建个图看一看，推一推）。