Reference：http://blog.csdn.net/jarjingx/article/details/8521690
其中伍昱的ppt不错。
2SAT最裸的模型：
一国有n个党派，每个党派在议会中都有2个代表，现要组建和平委员会，要从每个党派在议会的代表中选出1人，一共n人组成和平委员会。已知有一些代表之间存在仇恨，也就是说他们不能同时被选为和平委员会的成员，现要你判断满足要求的和平委员会能否创立？如果能，请任意给出一种方案。（ POI 0106 ）
analysis：比如有两个党派A、B，我们设A党派里两个代表为a和not a(即离散数学中的非a)，B党派里面为b和not b。
那么若满足((not a)->b)and((not b)->a)，则A和B可以都去。
SAT原本是个NP问题，但简单的2-SAT问题还是可以有效求解的。
基本解法：转化成图论问题
例如上面讲的问题，对每个党派K有两个节点k和not k。
如果对于两个党派A和B，如果这两个党派之间无法满足条件，那么在a和not b、b 和not a之间分别连边。
然后强连通分量缩点。如果对于一个党派K，k和not k在同一分量中，说明问题没有可行解。
否则有解。
---------------------------
离散数学终于派上用场了23333