\(n\) 个 bool 变量，有 \(m\) 个限制，形如：“第 \(i\) 个变量的真假性为 \(s\)，那么第 \(j\) 个变量的真假性需要为 \(t\)”，其中 \(i, j \in [1, n], s, t \in \{0, 1\}\)。求这些变量的一组合法取值，使得满足所有限制。
这里把限制简化为 \((\neg) i \rightarrow (\neg) j\)。建立 \(2n\) 个点，意义类似并查集。对应进行连边。注意对于限制，要给其逆否命题也连一条边。
我们做一个观察，首先对于能够到达的点，可以看成其直接相邻。然后考虑这样一个事实：如果 \(x \rightarrow \neg x\) 并且 \(\neg x \rightarrow x\) 那么 \(x\) 取 \(0, 1\) 都不对。这种情况是无解。如果 \(x \rightarrow \neg x\) 那么 \(x\) 只可以取 \(0\)。
于是我们想到按照拓扑序来搞。就是如果发现 \(x \rightarrow \neg x\) 那么令 \(x=0\)。\(x \rightarrow \neg x\) 说明一定 \(x\) 点的拓扑序在 \(\neg x\) 的前面，因此我们取拓扑序后面的那个点。
首先证明一下这个对所有图上的限制都不会违反。违反限制，也就是 \(x \rightsquigarrow y\) 满足 \(x\) 选了但是 \(y\) 没选。因为 \(x\) 的拓扑序在 \(y\) 前面，\(\neg x\) 在 \(\neg y\) 后面，所以如果选了 \(x\)，那么 \(\neg y \le \neg x \le x \le y\)，一定是 \(y\) 选了。
其次证明建出的图包含了所有限制。也就是说，如果不存在一条边使得起点满足并且终点不满足，那么就是合法的。通过真值表我们可以发现是对的，只有原命题和逆否命题有用。
于是我们只需要建图，kosaraju 判 scc 上有没有对边，然后拓扑排序即可。
标签：le,限制,变量,neg,拓扑,SAT,rightarrow From： https://www.cnblogs.com/Zeardoe/p/17205935.html