对称性

考虑 \(\tt 2sat\) 边的意义是：如果选取了 \(i\) 则必须选取 \(j\)，那么如果我们连边 \((i,j)\)，我们都是也需要连边 \((inv(y),inv(x))\)（\(inv(x)\) 即表示变量 \(x\) 的逆），因为原命题和其逆否命题真假相同。

那么发现这样建出来的图具有某种对称性，此性质是 \(\tt 2sat\) 算法最重要的性质。

解的构造

设 \(col_i\) 表示 \(i\) 所在强连通分量的拓扑序编号（编号小的拓扑序大），那么如果 \(col_i<col_{i+n}\) 我们选取 \(i\)；否则我们选取 \(i+n\)

要证明上述构造是正确的，我们只需要证明被选取点不能到达没有未被选取的点。使用反证法，假设存在被选取点 \(x\) 和未被选取 \(y\)，并且存在 \(x\rightarrow y\) 的路径，那么显然有 \(col_x\geq col_y\)，同时根据对称性，存在一条 \(inv(y)\rightarrow inv(x)\) 的路径，所以有 \(col_{y+n}\geq col_{x+n}\)

根据选取的关系可以知道：\(col_x<col_{x+n},col_{y}>col_{y+n}\)，所以可以推出 \(col_{x+n}>col_x\geq col_y>col_{y+n}\)，但是这与 \(col_{y+n}>col_{x+n}\) 矛盾，反证法证毕。

特殊的边

这里有一个小 \(\tt trick\)：如果 \(i\) 强制不能选取，那么可以连一条 \((i,inv(i))\) 的边，表示强制不能选 \(i\)

虽然这样连边不是对称的，但是用处还是很多：NOI2017 游戏

字典序最小的解

这种问题建议用直接 \(\tt dfs\) 的方法，也就是先搜字典序小的再搜索字典序大的。

这个问题也是可拓展的，既然是字典序问题就很容易和贪心产生联系：New Language

前后缀优化建图

本质思想还是建虚点来优化建图，连向这个虚点就代表了连向一个前缀\(/\)后缀。

如果你遇到要连向除一个点之外所有点的问题，那么可以拆成前缀与后缀的连边：Duff in Mafia