2-SAT

前置芝士：强连通分量。

先放一个板子题：2-SAT。

我们先考虑拆点，把每个变量 \(i\) 拆成两个点，\(i\times 2\) 和 \(i\times 2 + 1\)，前一个代表这个变量 \(i\) 取假，后一个代表这个变量 \(i\) 取真。

既然有了点，我们就要考虑连边。例如给一个条件：\(1\) 取 \(1\) 或者 \(3\) 取 \(0\)。我们就要建两条边，一条为如果 \(1\) 取 \(0\) 则 \(3\) 取 \(0\)，即 \(2\rightarrow 6\)；另一条为如果 \(3\) 取 \(1\) 则 \(1\) 取 \(1\)，即 \(7\rightarrow 3\)。

然后看一下这条边表示什么，表示的是一个要求是另一个要求的充分条件(建议学习一下充分条件与必要条件)。

那么，如果发现图中出现了 \(i\) 真是 \(i\) 假的充分条件；\(i\) 假是 \(i\) 真的充分条件，那么一定无解，因为不管 \(i\) 取什么，条件1总会要求你取 \(i\) 当前的值取反，这显然不可能成立。

换句话说，就是 \(\forall i\in[1,n]\) 如果 \(i\times 2\) 与 \(i\times 2 + 1\) 在一个强连通分量中，一定无解，否则有解。

说了这么多，我们终于说完了怎么判断有没有解，接下来说一下怎么构造解。