矛盾：如果边v在圆内，那么边u必然在圆外，则称v，u矛盾。
反矛盾：如果边v在圆内，那么边u必然也在圆内，则称v，u反矛盾。
判断说谎的条件：如果边v与边u既矛盾又反矛盾，那么必须说谎。
所以遍历所有的边组合，时间复杂度是O(n^2)，比2-SAT慢。
遍历所有的边组合(v,u)，如果v,u矛盾，那么将v,u并查集合并，并且记录v,u的关系为矛盾。（不矛盾的情况直接忽略）。
如果v,u关系为矛盾，u,w关系为矛盾，那么v,w关系为反矛盾。
并查集水过。

• 这是2-sat的朴素实现吧。。。 (0) Snow_storm 2011-02-21 16:33:48