简介
什么是2-SAT呢？就是有一些集合，每个集合中有且仅有两个元素，且不能同时选取两个元素，集合间的元素存在一定的选择关系，求解可行性及可行方案。
算法
1、连边
2、跑tarjan
3、判可行性，即同一集合中的两个点是否同属一个强连通块
4、缩点建新图，连反边
5、拓扑序，若当前点没有被访问过，则选择该点，不选择其另外的点
连边
2-SAT算法本身并不难，关键是连边，不过只需要充分理解好边的概念：a->b即选a必选b。
a、b不能同时选：选了a就要选b’，选了b就要选a’。
a、b必须同时选：选了a就要选b，选了b就要选a，选了a’就要选b’，选了b’就要选a’。
a、b必须选一个：选了a就要选b’，选了b就要选a’，选了a’就要选b，选了b’就要选a。
※a必须选：a’->a。
一些题目
POJ 3683 输出方案
POJ 3678 连边练习
BZOJ 1823 判断可行性
某不知名字的题目
题意：一开始有一些点与点的关系，问删除一些点之后，方案是否可行。
分析：删除点之后，原有的关系的连边会有所改变，因此对于每删除一些点，就要重新构图，跑2-SAT
资料
以上只是为了个人总结所用，所以并不是很详细。
需要的可前往：http://blog.csdn.net/jarjingx/article/details/8521690
