2-sat

萌新刚学 2-sat，写个题解练练手。

首先的话，我个人理解的 2-sat 就是对于每个数只有 \(2\) 种取值的问题。

这里我以 卡图难题 这题为例。

显然位运算的题，就是一个经典的 2-sat 的题，因为对于每个数都只有 \(0\) 和 \(1\) 两种选择。

那么我们将每个点 \(a_i\) 拆成 \(a_i\) 和 \(a_i+n\) 两个点，分别表示 \(a_i\) 的值为 \(0\) 和 \(a_i\) 的值为 \(1\)。

然后就是对于每种关系建边。

• \(a and b=0\)，那么 \(a=0,b=0\) 或 \(a=1,b=0\) 或 \(a=0,b=1\)，即 \(ins(a,b),ins(a+n,b),ins(a,b+n)\)。
• \(a and b=1\)，那么 \(a=1,b=1\)，即 \(ins(a+n,b+n)\)。
• \(a or b=0\)，那么 \(a=0,b=0\)，即 \(ins(a,b)\)。
• \(a or b=1\)，那么 \(a=1,b=0\) 或 \(a=0,b=1\)，即 \(ins(a+n,b),ins(a,b+n)\)。
• \(a xor b=0\)，那么 \(a=0,b=0\) 或 \(a=1,b=1\)，即 \(ins(a,b),ins(a+n,b+n\)。
• \(a xor b=1\)，那么 \(a=1,b=0\) 或 \(a=0,b=1\)，即 \(ins(a+n,b),ins(a,b+n)\)。

然后的话看有没有矛盾，即在图上跑一边 Tarjan，找出强连通分量，然后看有没有 \(a_i\) 和 \(a_i+n\) 同时在同一个强连通分量里面。

因为如果 \(a_i\) 和 \(a_i+n\) 同时在一个强连通分量中的话，那么 \(a_i\) 和 \(a_i+n\) 之间就可以互相到达，即 \(a_i\) 同时为 \(0\) 和 \(1\)，因此矛盾。