2-SAT:Poi0106PeacefulCommission[和平委员会]输入n（党派数），m（不友好对数）及m对两两不和的代表编号其中1≤n≤8000，0≤m≤20000分析：初步构图假设4个组，不和的代表为：1和4，2和3，7和3，那么构图：矛盾的情况为：存在Ai，使得Ai既必须被选又不可选。此算法正确性简要说明：由于Ai,Ai'都是尚未确定的，它们不与之前的组相关联，前面的选择不会影响Ai,Ai'。先看这样一个结构：对于原图中的每条边AiAj（设Ai属于环Si，Aj属于环Sj）如果Si≠Sj，则在新图中连边：SiSj通过求强连通分量，可以把图转换成新的有向无环图，在这个基础上，介绍一个新的算法。新算法中，如果存在一对Ai,Ai'属于同一个环，则判无解，否则将采用拓扑排序，以自底向上的顺序进行推导，一定能找到可行解。至于这个算法的得来及正确性，将在下一段文字中进行详细分析。深入分析：引理：原图具有对称传递性猜测1：图中的环分别对称推广1：新图中，同样具有对称传递性。分开来看，更加一般的情况，即下图：（说明：此图中Si'有可能为Si的后代节点）于是可以得到推广2：对于任意一对Si,Si'，Si的后代节点与Si'的前代节点相互对称。先提出一个跟算法1相似的步骤：如果选择Si，那么对于所有SiSj，Sj都必须被选择。而Si'必定不可选，这样Si’的所有前代节点也必定不可选（将这一过程称之为删除）。由推广2可以得到，这样的删除不会导致矛盾。每次找到一个未被确定的Si，使得不存在SiSi'选择Si及其后代节点而删除Si’及Si‘的前代节点。一定可以构造出一组可行解。因此猜测2成立。另外，若每次盲目的去找一个未被确定的Si，时间复杂度相当高。以自底向上的顺序进行选择、删除，这样还可以免去“选择Si的后代节点”这一步。用拓扑排序实现自底向上的顺序。算法2的流程：小结：全文总结：