基本思想是按某种顺序为每一对未确定的 \((a,\neg a)\) 确定一个合法的点并将其后代加入方案。如果本次选择了 \(a\)，其合法等价于之后选到的 \(a\) 的后代不会同时包含某个点对\((b,\neg b)\)。其可以细分为：①之后选到的 \(a\) 的后代不包含先前已被加入到方案的点的反面，这里所说的一个点的反面指其所在点对的另一个点。② \(a\) 的后代不同时包含未被选过的点对（也不包含 \(\neg a\)）。
在进行强连通分量缩点后，我们知道如果 \((a,\neg a)\) 存在于同个分量内，则一定无解。下面我们证明一个命题：只要没有 \((a,\neg a)\) 存在于同个分量内，就一定有解。之后的讨论都在没有 \((a,\neg a)\) 存在于同个分量内的情况下进行。
2-SAT 的构图是对称的，即如果存在 \(a\to b\) 的边，则必然存在 \(\neg b\to \neg a\) 的边。此处的边可以进一步泛化为可到达关系。因此有一个结论：当为 \((a,\neg a)\) 确定一个点加入方案的时候，不需要考虑这次选择可能会对先前已经被加入的点及其所在的点对造成的影响。即，当前的每一对未确定点对的点均满足①。
这是因为，一个点被加入方案时，会把它的所有后代全部加入方案，现在我们既然在确定选 \(a\) 或 \(\neg a\)，这说明两者皆没有被选过，即两者都不会是先前选过的点的后代，由对称性，这两者也不会是先前选过的点的反面的前代，故选择这两者中的任意一方都不会强制选到先前的点所在点对的另一个点。所以，如果我们选了 \(a\) 后，只要 \(a\) 满足 ②，这个 \(a\) 就一定合法，不用考虑后效性。
当现在考虑到点对\((a,\neg a)\) 时， \(a\) 不合法等价于存在这样一个关系 \(a\to b \and a\to \neg b\)，由对称性，这进一步等价于 \(a\to \neg a\)。由于 \(a\) 与 \(\neg a\) 不在同一分量内，所以一定不存在 \(\neg a \to a\)。这引出了第二个结论：如果 \(a\) 不满足②，\(\neg a\) 一定满足②。综合上面两个结论，每个点对中至少有一个点①②同时满足，这就证明了命题。
上述的讨论启发我们一种构造：每一轮找到一个未选择的点对，如果存在一条边（或可达关系）则选择边的终点，如果不存在边则随意选择一个点加入方案，并接着加入所有后代节点。这个构造可以覆盖所有的解，不过求一个解的复杂度还较高，是 \(O(nm)\) 的。
我们可以进一步简化构造。考虑点 \(a\) 的拓扑序 \(t_a\)，对于 \(a\) 的所有后代 \(b\)，有 \(t_a<t_b\)。并且，每个 \(b\) 对应的 \(\neg b\) 都是 \(\neg a\) 的前代，\(t_{\neg a}>t_{\neg b}\) 。因此，我们对每个点对选择拓扑序更大的那个点 \(a\)，就会有 \(t_{\neg b}<t_{\neg a}<t_a<t_b\)，\(a\) 的后代 \(b\) 在自己的点对中也是拓扑序更大的那个，免去了枚举后代节点的过程，可以做到真正的 \(O(n+m)\)。
标签：方案,一个点,加入,neg,后代,构造,选过,SAT From： https://www.cnblogs.com/nkxjlym/p/18427187