2-SAT

2-SAT 实际上是在标记 $A\Rightarrow B$ 这样的关系，用每个点去表示一个命题。在图上对命题成立和不成立分别建立点 $x_i$ 和 $\neg x_i$。命题和图上的边的关系如下：

• 等价的命题 $A\iff B$：在 $a$ 和 $b$ 之间连接双向边，在 $\neg a$ 和 $\neg b$ 之间连接双向边
• 充分条件 $A\Rightarrow B$：连接边 $a\to b$ 和边 $\neg b\to \neg a$
• 或关系 $A\vee B$：连接边 $\neg a\to b$ 和边 $\neg b\to a$
• 必然 $A$：连接边 $\neg a\to a$

扩展域并查集

扩展域并查集应该一定能解决所有边都是双向的情况。

IMPORTANT

扩展域并查集的本质是维护异或/同或关系。它不能维护或/与这类不对称的关系，例如：

• 或关系：$\neg a\Rightarrow b$ 和 $\neg b\Rightarrow a$ 都不是等价关系；
• 异或关系：$\neg a\iff b$ 和 $\neg b\iff a$ 都是等价关系。