一些布尔变量组成若干二元简单析取式，求使得这些简单析取式全部为真的赋值方案。

要不我们先建个图？

一个布尔变量有真假两种情况。所以我们令点 $u_i$ 代表第 i 个变量为真，点$u’_i$ 代表第 i 个变量为假。

然后我们搞一点事情。考虑一个点 $u’_i\in V$ ，即 $b_i=0$，要想 $b_i\vee b_j$ 为真，必须有$b_j=1$ 即 $u_j\in S$。

……那我们顺手连个边好了。

记一个简单析取式为两个有序二元对，就这样连边：

$\forall (b_i,b_j)\rightarrow (u’_i,u_j) \in E$

现在我们有一个完整的图 $G$ 了。

那么一个合法解就是图 $G$ 的一个点集。

随便选一个点，把它加入解集，为了使原式成立，那么它能到达的所有点也应该加入解集。这是我们刚刚讨论过的。

对于一个强连通分量，如果我们把其中任意一个点加入解集，那么整个分量都会在解集中。

这是捆绑销售，不能只要一个点。

所以如果 $u_i,u’_i$ 在同一个强连通分量中，那么gg，一个变量不能又真又假。

如果不存在这种情况，我们就可以缩点得到 DAG 。由于无法导出矛盾，所以一定可以得到一个解。

所以可行性的判断只需要 Tarjan 之后对于每个 SCC 检查一下就好啦。

toposort自底向上，我也不太会，请去看论文。

字典序最小方案

建图是一定要建图的，这辈子都不可能不建图的。$O(M)$ 求方案又不会，只有搜索才能骗骗分数这样子。

理论上 $O(NM)$ 的复杂度，实际上跑的不知道快到哪里去了。

遍历每个布尔变量，如果真点或假点已经在点集中了，那么考虑下一个布尔变量，否则把真点加进去试一下，如果不行再加假点，如果还不行，说明无解，退出。否则进行下一个。

需要说明的是，这种做法不需要回溯。也就是说对于一个布尔变量，如果真假都不行，整个问题就无解，而不是回溯到前一个布尔变量调整真假。这是因为我们考虑的布尔变量没有被赋值，这说明前面的布尔变量对应点到这个布尔变量对应点没有边。没有边，调整他们的真假也是没用的。

这个太裸了。出题人不可能让你写裸题吧。所以我们的二元运算不仅可以是析取（OR），还可以是XOR，AND，以及任何能构造推出关系的运算……

实际上，图 $G$ 中的边表示“推出”这一含义。

为了缩短篇幅，我们用 $x,y$ 表示两个布尔变量，列几种典型操作的推出关系。

AND 非常特殊，它要求两个变量都为真。

我们先介绍如果要求一个变量必须为真时的做法。

$!x\rightarrow x$

显然，这是个矛盾式。如果我们把它加到图中，那么一旦选择了 $x$ 的假点，就会不可避免的顺着边到达 $x $ 的真点，从而推出矛盾。所以所有选择 $x$ 的假点的情况都会变成非法情况从而排除。

那么 AND 的做法也就显而易见了。

NOT XOR

XOR 可以看成相异操作，那么 NOT XOR 就是必须相同。

NOT AND

用摩根律转化为OR。