问题：微软笔试题——http://hihocoder.com/problemset/problem/1108 最初想法，仍有待验证：http://bbs.bccn.net/thread-441260-1-1.html 最初想法是：只有成对出现的约束，1 2 0，才能够对问题进行限制，对问题结果照成影响，因此只需要考虑成对出现的约束
问题：微软笔试题——http://hihocoder.com/problemset/problem/1108
最初想法，仍有待验证：http://bbs.bccn.net/thread-441260-1-1.html
最初想法是：只有成对出现的约束，1 2 0，才能够对问题进行限制，对问题结果照成影响，因此只需要考虑成对出现的约束。对于成对出现的节点，在构图中有
1 2 1
无向边 进行连接，然后检测最终构图中是否存在节点个数为奇数的环，从而得到最后的结果。
解答：http://blog.csdn.net/kk303/article/details/42869039
由对称性解2-sat问题：http://wenku.baidu.com/link?url=G8jqWFFet0uc164GJnXwyCtJRoi0DQH0U1aoDIRdI7sdSS7R7-h6iacr4cENA808XvkbUV7Atj3MZxTP_r4gksh_IwXV1Bn76YRRMTwSIWq
1.问题模型：
存在n组元素
A1
A2
A3
...
An
~A1
~A2
~A3
...
~An
规定每组元素中能且仅能选择一个，同时给定m组约束（Ai，Aj），约束也可能是（Ai，~Aj）。一组约束中的两个元素相互冲突，不能同时被选择。
求解是否能在约束限制下，在n组元素中选择出n个元素。若能，进行选择。
2.解法：步骤（1）：对每对约束（Ai，Aj）。因为存在关系选择 Ai 则必须选择 ~Aj ，而选择 Aj 则必须选择 ~Ai ，因此在构图（ 图的节点个数为2n）时，对于 （Ai，~Aj）， （Aj，~Ai）添加 有向边 。
步骤（2）：在构图中查找极大强连通分量。将强连通分量转化为节点。这个步骤叫做缩图。
步骤（3）：查找是否存在 （Ai，~Ai）处于同一个强连通分量中，如果存在，问题无解，程序终止。
步骤（4）：根据拓扑排序找到一个可行解。