2-SAT

[Ir1d]

https://oi-wiki.org/graph/2-sat/

[AndrewWayne]

认领施工？

[gblong10]

Party那道题会MLE吧，4000400太大了，开1000010就可以了

[Tsukihi-Araragi]

请问这个爆搜的复杂度是不是可以卡到 o(n^2)?

[Conan-shen]

输出方案那里是不是有问题呀

1. 在反拓扑序中 x在 \lnot x 前面，那么x为true -> 在拓扑序中 \lnot x 在 x 前面，那么x为true。

[thallium]

定义感觉用正常的逻辑表达式更好一些？

[pealfrog]

@Tsukihi-Araragi
请问这个爆搜的复杂度是不是可以卡到 o(n^2)?

应该可以卡到 O(nm)

[jpy-cpp]

暴搜打错了///

[abcdhhhh]

另外还有个Horn-sat问题，就是每个子句最多只含一个肯定变元。具体做法是给每个单一肯定变元的子句赋好值，并在其他子句中去除该变元；当没有单一肯定变元时，给其他变元都赋值0即可

[F1shAndCat]

缩点建图那里是不是应该 (a1,b2) 和 (a2,b1) 存在两个矛盾?不然不应该同时建三条边吗