对于2-sat问题的求解 一.O(n+m) 暴力不多说 二.O(m) 1.构图 2.求图的极大强连通子图 3.把每个子图收缩成单个节点,根据原图关系构造一个有向无环图 4.判断是否有解,无解则输出(退出) 5.对新图进行拓扑排序 6.自底向上进行选择、删除 7.输出 对于此问题有两篇论文可看: 伍昱 由对称性解2-sat问题(ppt) 赵爽 2-sat解法浅析(pdf)