问题：微软笔试题——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）：根据拓扑排序找到一个可行解。