.png)
做了一些题之后渐渐懂了一些，有了一些自己的见解。
它能解决一类问题类似一个序列，每个位置只有两个取值，然后取值间有一些限制，求解其是否有解以及求一个可行解。
考虑每个位置拆分为两个点，分别为 i 和 \neg i，代表着两个取值 true 和 false。
考虑将这些点连起来形成一张有向图，一条 u 向 v 的边表示，一旦满足选择 u，那么一定会选择 v。
比如 \neg i 连向 j 就表示 i 取值为 false 时，j 一定取值为 true。
那么此时对其进行 tarjan 缩点，被缩成了一个 DAG。
那么如果存在一个 i，所代表它的两个点 i 和 \neg i 在同一个强联通分量中，显然是无解的，于是整个问题就无解了。
考虑 i 如何取值，考虑这个 DAG 的反拓扑序，那么肯定会选择 i 和 \neg i 中在反拓扑序靠前的那个。
因为选择反拓扑序中靠后的那个有可能会导致另一个也需要成立，于是选择反拓扑序中靠前的那个。
缩点后的反拓扑序刚好就是 tarjan 缩点时对 SCC 的编号，于是判断代表两个取值的两个点的反拓扑序相对位置就知道选哪个了。
然后还有一个很重要的引理。
引理：
设代表第 i 个位置值为 x 的点为 u_{i, x}。
对于每条边 u_{i, x} \rightarrow u_{j, y}，一定存在着另一条边 u_{j, y \oplus 1} \rightarrow u_{i, x \oplus 1}。
证明也很好证明，可以反证法。（应该是这样的吧，没有伪吧？）
因为条件都是形似 i 为 x 或者 j 为 y，那么就可以转化为 i 不为 x 则 j 为 y，以及 j 不为 y 则 i 为 x，这就是引理中的定理，有的时候不考虑引理会导致漏边从而导致错解。
考虑拎出来环，把环抽象成一个圆，于是就是圆上有若干条弦，交叉的两条必须得拿出去一条，于是就出现了要不 i 在内要不 j 在内，交叉的两个取值不得相等，于是就设 \neg i 为在外面，i 是在里面，对于交叉的两条弦 i 和 j，连接 \neg i \rightarrow j，i \rightarrow \neg j，j \rightarrow \neg i，\neg j \rightarrow i。
直接成无向图了（bushi）。
只是要理解 2-SAT 的话，这两个例题就能够理解了，其实做一个板题就能理解了。
蒟蒻的一些见解，球球给我挑错，如果我有理解错的地方，求拷打。