一、2-SAT

2-SAT 问题是给定 \(n\) 个变量 \(x_1, x_2, \dots, x_n\)，取值只有 \(0\) 或 \(1\)，然后这些变量要满足一些条件，比如：如果 \(x_1 = 1\) 那么 \(x_2 = 0\) 之类的。

然后我们要解决的问题就是判定是否存在一组 \((x_1, x_2, \dots, x_n)\) 满足条件，如果存在输出方案。

考虑建图。将每个变量 \(x_i\) 建成两个点，\(i_0\) 和 \(i_1\)，即 \(x_i = 0\) 和 \(x_i = 1\)。从 \(i_k\) 连到 \(j_l\) 就表示推理如果 \(x_i = k\) 那么 \(x_j = l\)。

然后我们要判断是否有解。先对原图缩强连通分量，如果 \(i_0\) 和 \(i_1\) 在同一个 SCC 里就矛盾，即无解；就是如果 \(x_i = 0\) 可以推到 \(x_i = 1\)，又可以推到 \(x_i = 0\)，显然矛盾。

考虑输出方案，设 \(scc_u\) 表示节点 \(u\) 所在的 SCC 的编号。如果 \(scc_{i_0} > scc_{i_1}\)，那么说明 \(i_0\) 的拓扑序在 \(i_1\) 之后，说明 \(x_i = 0\)，否则 \(x_i = 1\)。