求解 2-SAT 问题
$2-\rm Sat$ 问题是求解某个 $\rm bool$ 方程组，方程组中的每个方程被描述为：$x_i$ 为真$/$假 或 $x_j$ 为真$/$假。
我们可以对每个 $x_i$ 和 $\lnot x_i$ 分别建点，$x_i$ 为假看作 $\lnot x_i$ 为真，这样方程就仅有一种类型了，即若 $p$ 为真则 $q$ 为真。具体来说，建一些边 $u\to v$ 表示当 $u$ 为真的时候 $v$ 一定为真，比如有方程 $p$ 为真或 $q$ 为真时，建两条边 $p\to \lnot q$ 和 $q\to \lnot {p}$。
建完图后，显然同一个强连通分量中的点取值必然相同，那么如果 $a$ 和 $\lnot a$ 在同一个强连通分量里则该 $\rm bool$ 方程组无解。易知，存在 $a$ 和 $\lnot a$ 在同一个强连通分量中为该 $\rm bool$ 方程组无解的充要条件。
对于其它的点，每对 $a$ 和 $\lnot a$ 中有且仅有一个为真，我们令拓扑序大的那个为真。可以分情况证明其最优性 ：
- 若 $a$ 和 $\lnot a$ 在 $\rm DAG$ 的同一条链上，那么拓扑序大的必然为真，否则两个都为真与题意相悖。
- 若 $a$ 和 $\lnot a$ 在不同链上，那么两个点的取值其实无所谓，但一定要跟拓扑序相关。因为每条链上拓扑序的大小关系时严格的，用拓扑序规定某个点取值是否为真可以使为真的点在同一条链上，尽可能降低对其他点的影响。另外，为了保证跟上一种情况的统一性，仍选择令拓扑序大的点为真。
另一方面，我们发现 $\rm Tarjan$ 缩点所求出的 $\rm SCC$ 强连通分量数组的值负相关，可以理解为拓扑序更小的点更后入栈，也更先出栈编号。故最后对比 $a$ 和 $\lnot a$ 的 $\rm SCC$ 值即可判断它们谁为真谁为假。
经典例题
[LG6378] Riddle
对树上每个点建立一个 $\rm bool$ 变量，取值为 $1$ 表示这个点选。
使用 $\rm 2-Sat$ 的通用做法，建立为每个点的状态建立两个点 $u$ 和 $\lnot u$，分别对每个限制考虑 ：
- 每条边至少有一个关键点，则对于一条边 $u-v$ 若 $\lnot u$ 则 $v$，若 $\lnot v$ 则 $u$，故连接 $\lnot u\to v$ 和 $\lnot v\to u$。
- 每个部分最多有一个关键点，则如果 $u$ 被选了，那么同一个块中所有点都不能选，连接 $u\to \lnot v$。 但是我们发现这样连边是 $\Theta(n^2)$ 的，所以前缀和优化连边即可。
建好图以后直接跑 $\rm 2-Sat$，时间复杂度 $\Theta(n)$。
[POI2011] KON-Conspiracy
首先转化题意，这道题要求的是将一张无向图划分成一个团和一个独立集的方案数。
首先找出一种合法的方案是很容易的，是一个裸的 $\rm 2-Sat$ 问题。
考虑找出一种方案后统计方案数。首先有如下性质 ：
- 一个团中不可能取出一个以上的点加入独立集，因为两点之间必有连边。
- 一个独立集中不可能取出一个以上的点加入团，因为两点之间必无连边。
所以可以直接分别枚举团和独立集中的每个点，交换它们即可。
时间复杂度 $\rm \Theta(n^2)$。
[北京省选集训 2019] 完美塔防
首先预处理哪些炮台会互相打到，若存在，则输出 IMPOSSIBLE.
然后发现有如下结论：
每个空地最多可以被两个炮台打到。
因为每个空地最多在纵横两个方向上被打到，若还存在一个，则必定会打到其中一个炮台。
于是对每个炮台，它的纵横情况设为 $0/1$，每个空地会加入一个形如 $a~or~b$ 的条件，这就变成了经典的 $\rm 2-Sat$ 问题。
时间复杂度 $\Theta(Tn^3)$。
[HNOI2010] 平面图判定
首先有平面图中的欧拉定理，设一张无向连通图点数为 $v$，边数为 $e$，面数为 $f$，则有 ：
$$v-e+f=2
$$
考虑通过对 $e$ 进行归纳证明该式。
当 $e=0$ 时显然成立。
若当 $e'=e-1$ 时该式成立，我们要证 $v-e+f=1$ 成立只需证添加一条边会使得面数恰好增加 $1$。 而对于这个问题，我们可以分类讨论，若这条边加在某个面的中间，那么其必将这个面分成两半，若这条边加在图形外面，那么会围出一块新的区域，也会使面数恰好增加 $1$。
故该式成立。
我们进一步探究平面图的性质。定义面的度数为与其相邻的面的数量，显然对于每条边都会有恰好两个面与其相邻，故所有面的度数之和为 $2e$。 又因为每个面至少三条边，所以度数不小于 $3$，进而有 $3f$ 不大于所有面的度数之和，故有 $3f\leqslant 2e$，将其带入平面图中的欧拉定理可得 ：
$$e\leqslant 3v-6
$$
于是不满足该式的无向连通图均不为平面图，进而可以将 $m$ 限制到与 $n$ 同数量级。
我们发现题目给定了哈密顿回路，于是考虑以这个环作为中心考虑问题。
我么发现对于任意一条边，它要么从环内连接，要么从环外连接，并且如果有两条边 $u-v$ 和 $u'-v'$，且满足 $u<u'<v<v'$，那么它们不能连在同一面。于是可以通过这种关系构建 $\rm 2-Sat$ 模型。
时间复杂度 $\Theta(Tn)$。