对于2-sat问题的求解

一.O(n+m)

暴力不多说

二.O(m)

1．构图
2．求图的极大强连通子图
3．把每个子图收缩成单个节点，根据原图关系构造一个有向无环图
4．判断是否有解，无解则输出（退出）
5．对新图进行拓扑排序
6．自底向上进行选择、删除
7．输出

对于此问题有两篇论文可看：
伍昱 由对称性解2sat问题（ppt）
赵爽 2sat解法浅析（pdf）

上一篇：[HDU4348]To the moon（主席树）

下一篇：【模板】splay

---

模板 2-sat