2013-team4/code/2-sat

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
2-SAT 判定：

从n个2元group中每个group选出一个东西，某些东西不能同时被选中，判定是否存在选择方案。
当group[i][1]和group[j][1]冲突时，给group[i][1]连接一条边到group[j][2]，group[j][1]连接一条边到group[i][2]，
表示选group[i][1]则必须选group[j][2]，其余类推，得到一个有向图。
某个东西必须被选：若group[i][1]必须被选，从group[i][2]连一条边到group[i][1]
求这个有向图中的强连通分量，若某组group[k][1]和group[k][2]在一个强连通分量里，则无法满足此约束。
}}}

2-SAT 判定：
从n个2元group中每个group选出一个东西，某些东西不能同时被选中，判定是否存在选择方案。
当group[i][1]和group[j][1]冲突时，给group[i][1]连接一条边到group[j][2]，group[j][1]连接一条边到group[i][2]，
表示选group[i][1]则必须选group[j][2]，其余类推，得到一个有向图。
某个东西必须被选：若group[i][1]必须被选，从group[i][2]连一条边到group[i][1]
求这个有向图中的强连通分量，若某组group[k][1]和group[k][2]在一个强连通分量里，则无法满足此约束。