2-SAT 问题
第一种定义ψ(｀∇´)ψ
给你 \(n\) 个二元组 \((x_0,x_1)\)，有 \(m\) 个限制条件，形如 \(<a,b>\) ，表示 \(a,b\) 相互矛盾，不能同时选中 \(a,b\) 这两者。
且 \(a,b\) 属于不同的二元组。
问是否存在一种方案，使得每个二元组里都恰好有一个元素被选择，且所有条件不会被违背。
如果有，需要构造方案。
第二种定义ψ(｀∇´)ψ
给你 \(n\) 个元素，有 \(m\) 个限制条件，形如 \(<a,b>,<f_a,f_b>\) ，即，如果 \(a\) 的状态是 \(f_a\) ，那么 \(b\) 的状态必须是 \(f_b\)。
\(f_i\) 的值只可能是 \(0,1\) ，表示选或者不选 \(i\) 这个元素。
问是否存在一种使得所有限制被满足。
如果有，需要构造方案。
以上两种定义本质上是完全一样的，只不过说法不太相同。
做法ψ(｀∇´)ψ
发现所有的约束条件都可以归化成这样的一个命题：
若 \(p\)，则 \(q\)。
也就是 \(p \Rightarrow q\)。
所以可以考虑把这个命题看作有向边，就可以转化成图论的模型。
从第二种定义考虑， \(p,q\) 就表示两个元素的选或者不选的状态。
考虑拆点，把一个元素 \(x\) 拆成 \((x_0,x_1)\) 两个元素，分别表示元素 \(x\) 不选还是选。
实现的时候可以把图分成节点对称的两部分 \(1\to n\) 和 \(n+1 \to 2n\)。
实际上边也应当是对称的，之后会说。
然后就可以比较方便的连边了。
比如，如果选了 \(a\) 就不能选 \(b\) 这个约束条件。
就可以连一条有向边 \(a_1 \to b_0\)。
但是这个东西是一个命题 \(p \Rightarrow q\) 啊，所以它的逆否命题 \(\lnot q \Rightarrow \lnot p\) 也是成立的。
那么在连 \(a_1 \to b_0\) 的同时也需要连上 \(b_1 \to a_0\)。
所以如果把有向边看成无向边，图也是对称的。
不过有一种特殊的情况，我们需要强制选 \(a\)，那么这个时候就需要连一条边 \(a_0 \to a_1\) 。
这样的话，如果选 \(a_0\) 就会矛盾（具体看下面），就达到可强制选 \(a_1\) 的目的。
可以发现，同一个强连通分量里的所有变量的取值是相同的。
比如这个强连通分量长这样（可能不一定会出现这样的情况，不过感性理解就行）：
\(a_0 \to b_1 \to c_0 \to a_0\)。
那么 \(a_0\) 的取值如果为 \(\text{true}\) （不选择 \(a\)），那么 \(b_1\) 的取值也应当为 \(\text{true}\)，同理 \(c_0\) 的取值也是 \(\text{true}\)。
所以考虑缩点， 发现如果一个元素的两种状态处于同一个集合，那么必然是无解的，因为你不可能选一个物品又不选一个物品。
缩点完之后，这个图会成一个 DAG。
但是它仍然可以分成两个部分，新图上 \(c[x_0]\) 和 \(c[x_1]\) 的关系就可以看成 \(x_0\) 和 \(x_1\) 的关系。
对于原来有的一条边 \((x,y)\)，在新图上连接 \((c[x],c[y])\) 即可。
发现在新图上选择一个零出度点不会对其他的点造成什么影响，那么就不断的找零出度点即可。
这个过程就是反着的拓扑排序。
那么在这个新图的反图上跑拓扑排序，对于每个点打一个标记 \(color\)，表示这个 SCC 当中的所有变量的取值。
如果当前点 \(u\) 的 \(color\) 没有被标记过，那么给他标记为 \(0\)，并把这个点对应的点 \(v\) 标记为 \(1\)。
对应的点就是满足类似原图 \(x_0\) 和 \(x_1\) 的关系的点。
然后就得到了一组可行解。
但是因为 Tarjan 完之后的 SCC 编号就是逆拓扑序，所以直接正序扫描所有 SCC 就行了。
给一组对应点当中拓扑序更大，也就是编号更小的的一个点染色成 \(0\) ，另外一个染色成 \(1\) 即可。
实现可以不用判每个元素的状态变量所在的 SCC 的颜色，只需要比较编号大小就行。
1 2 3 4 5 6 7 8 9 10 11 | |
还有一种爆搜做法，但是觉得不喜欢（
毕竟 Tarjan 写起来方便，常数也小。
注意，点相关的数组一定要开两倍，边相关的需要计算然后开对应倍数。
如果两个变量的四种取值之间没有任何的约束关系（也可以理解成不矛盾），是不用连边的。