Katu Puzzle

很神奇的2-SAT问题。找了一篇赵爽的《2-SAT解法浅析》。作者是高中生啊，查了下却发现是05年交大ACM总冠军队的成员……Orz

题目抽象出来后就不难做了，建一个含2*N个点的有向图，边由逻辑运算给出，边(u,v)表示选了u点则必须选v。编号为i的点对应图中i*2和i*2+1的两个点，分别表示i点取值为1、0。点A、B间由逻辑运算生成的边如下：

A & B == 1: 增加边(A*2+1,A*2)和(B*2+1,B*2);

A & B == 0: 增加边(A*2,B*2+1)和(B*2,A*2+1);

A | B == 1: 增加边(B*2+1,A*2)和(A*2+1,B*2);

A | B == 0: 增加边(A*2,A*2+1)和(B*2,B*2+1);

A ^ B == 1: 增加边(A*2,B*2+1)、(B*2+1,A*2)、(A*2+1,B*2)和(B*2,A*2+1);

A ^ B == 0: 增加边(A*2,B*2)、(B*2,A*2)、(A*2+1,B*2+1)和(B*2+1,A*2+1);

建好图后求强连通分量。最后判断是否对所有的i=0:N-1,是否有i*2和i*2+1不在同一强连通分量中，若成立则原问题有解，否则无解。

这里被 A & B == 1 和 A | B == 0 卡了一下……不可取的点直接引入必败边的做法非常巧妙……

同样分别使用了两次DFS和tarjan来求强连通分量，代码分别如下：