或曰，有学长两天授吾以十专题，吾顿感日月之紧迫，以专题竟不能以吾之所有，遂成此文，以记之
语文确实没学好
本文可能涵盖多个知识点，故每个的讲解比较简略，仅供参考
一. 2-SAT
$ 2-SAT $ 用于求解一个变量只有两种情况的适应性问题（就是有没有解以及输出一种方案）；
其实可以类比二分图最大匹配（但其实两者的差别还是很大的）；
算法流程
对于每一个变量，我们都有两种情况，$ true $ 和 $ false $；
而题目中给我们的，是形如 {$ A = true / false $ 或 $ B = true / false $} 的若干个二元组，问是否能够全部满足；
考虑对于{$ A = p $ 或 $ B = q $}， 我们可以有如下的伪代码：
if (A == p) B 可以为 q 或 !q
if (A == !p) B 只能为 q
if (B == q) A 可以为 p 或 !p
if (B == !q) A 只能为 p
我们不难发现，对于第二种和第四种情况，我们是可以确定 $ A $ 和 $ B $ 的；
因此，我们可以依据这个性质，进行加边操作：
$ A_p \rightarrow B_q $ 这条边代表当 $ A $ 为 $ p $ 时，$ B $ 只能为 $ q $；
这样建好图后，我们要判断无解；
引理1： 若 $ A_p $ 与 $ A_{!p} $ 在同一强联通分量中，即无解；
显然；
求法：$ Tarjan $；
对于有解的情况，题目要求输出一种方案，有以下引理：
引理2： 对于$ A $ 的两种情况 $ A_p $ 与 $ A_{!p} $，若选择两者拓扑序较大的（ $ Tarjan $ 遍历顺序较小的）作为答案，则满足要求；
这里的“满足要求”指的是满足要求的多种情况中的一种情况；
其实稍微思考一下，不难发现拓扑序较大的节点需要满足的条件较少，所以更容易满足要求；
至于证明，我来浅浅的证明一下：
证：
考虑采用反证法；
设 $ f( A_p ) $ 表示缩点后 $ A_p $ 所在强连通分量的拓扑序；
设有：
\[f(A_p) < f(A_{!p}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f(B_{!q}) < f(B_q) \]且存在路径：
证毕；
标签：狂补,专题,false,暑期,满足要求,引理,true,杂项,SAT From： https://www.cnblogs.com/PeppaEvenPig/p/18320582