关于2-sat问题，这里笔者主要是做一些简记，如要详细了解，可以读一读此dalao的文章：https://blog.csdn.net/jarjingx/article/details/8521690
2-sat问题的定义：简单来说，一般的2-sat问题就是给定许多只有两个元素的集合，给你一些规则和约束（比如选了A就不能选B），然后从每个集合中（必须且只能）选出一个元素，问是否有可行方案。
2-sat问题出题一般比较裸，因此考到的话也不会很难。
首先给出常用的建边模型：
模型一：两者（A，B）不能同时取
那么选择了A就只能选择B’，选择了B就只能选择A’
连边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→B，B→A，A’→B’，B’→A’
模型四：两者（A，A’）必取A
连边A’→A
2-sat问题一般解决步骤：
（1）按模型连边建图G
（2）Tarjan缩点，再反向建图RG
（3）一般来说，如果有某一组对应点在同一个强连通分量中，则无解，反之有解
（4）如果有解且要求输出一种方案，拓扑排序RG，在排序过程把每个点染色为可行或不可行
（5）依次输出染色为可行的点
UPDATE ：不用建反图拓扑排序，如果要输出方案，只需要tarjan缩点染色后执行以下代码：
for(int i=1;i<=n;++i)
val[i]=c[i]>c[i+n];
你没看错真的就这么简单。val[i]为0表示第i个二元组（Ai,Bi）选Ai，否则选Bi。