2

2 - SAT 大概是要满足以下关系:

　　现在有一个集合，你现在要把这个集合里面的所有元素都分成两个集合，给定许多个诸如此类限制条件：

　　1.x0与y0必须在同一集合内

　　2.x1与y1必须在同一集合内

　　3.x2与y2必须在同一集合内

　　.....

　　现在要你判断是否能将原有的那个集合分成两个集合

思路 ：

　　1.首先用tarjan缩点，处于同一个强连通分量里面的元素则必须都放置在同一个集合内

　　　 2.用缩点后的点来建一个反图

　　　3.寻找对立点，对于上面限制条件中，如果x，y属于不同的强连通分量中，那这两个强连通分量就是对立点

　　　 4.拓扑排序。每次找到一个点,如果它上面没有打标记,打上选择标记,并把其对立点，打上不选标记

　　如果成功就是可行的.