2-sat 2个条件自适应问题 也就是说n个变量 每个变量都有两个取值 要求：求出一组方案满足一些限制。值得一提的是 k-sat是完全NP问题 无法在多项式时间内解决。
想要解决2-sat问题 第一种方法 爆搜，第二种方法 图论 因为我们没有一种好的方法去解决这个问题 可以考虑转换为图论模型也是最特殊的一种解决方法的问题.(毕竟看起来这个东西至少网络流建图是非常困难的。
解决方法：
发现每个点要么取0要么取1 对于一个点我们 建两个点 \(a_i\)和\(a_{i+n}\)来表示当前这个点选0和1。
连边L：规定一条有向边\(x->y\)来表示如果选择了x就必须选择y。下面是一些常规的满足限制的建图.
\(i,j\)不能同时选，那么说明选\(i\)必须选\(j'\)，选\(j\)必须选\(i'\) 那么显然\(i->j'\) \(j->i'\);
\(i,j\)要么都取要么都不取，说明选\(i\)必须选\(j\),选\(j\)必须选\(i\)，考虑一下关系的逆否性我们也可以得出选\(i'\)必须选择\(j'\)，选\(j'\)必须选\(i'\),那么\(i->j\),\(j->i\),\(j'->i'\),\(i'->j'\);
\(i,j\)不能同时不取(至少选择一个)：选了\(i'\)就要选择\(j\)选\(j'\)就要选择\(i\),\(i'->j\),\(j'->i\);
\(i,i'\)必须取i那么\(i'->i\)这连边的含义是由于我们选择\(i'\)就是不满足要求的因为此时\(i\)就选择不了了我们强制选择\(i'\)时选择\(i\)就行了。
\(i,j\)必须不相同即 要么选\(i\)要么选\(j\),选\(i\)必选\(j'\)选\(j\)必选\(i'\)选\(i'\)必选\(j\)选\(j'\)必选\(i\),那么显然\(i->j'\),\(j->i'\),\(i'->j\),\(j'->i\);
剩下的一些关系不再赘述 一般我们除了考虑关系的正向性还要考虑关系的逆否性.
关于最后判定合法问题 研究了一会 理解不算太深 大体如下：
首先缩点，我们发现最后剩下一张DAG在这张图上我直接选择一个入度为0的点会牵连到一堆点显然选择关系是很难传递下去的。
于是考虑一下我们每次都选择一个出度为0的点这个点对后续没有任何影响只对前面的的点具有一定的影响。
显然这种不选择关系是可以传递的。
考虑反向建图我们不断选取 入度为0的点即出度为0的点 对后面没有影响并且传递不选信息。
然后不断这样进行下去我们就构造出来了一组合法解。
进一步的 我们发现 在反图上的拓扑序就是我们点双联通分量的标号。
由刚才的结论 拓扑序小的先选我们可以直接利用点双联通分量的判断来进行判定。
原文：https://www.cnblogs.com/chdy/p/12182089.html