适应性问题

存在若干命题 \(p_i\)，以及若干形如 \(x_{k_1}\lor x_{k_2}\lor\dots\lor x_{k_n}\) 的 \(s_k\)，其中 \(x_i\) 为 \(p_i\) 或 \(\lnot p_i\) 其中一个。

要求是否存在一个命题的取值集合使得条件 \(s\) 均成立，其中每个条件最多包含 \(n\) 个命题，这样的问题称为 n-SAT 问题，\(n\ge 3\) 的情况已被证明为 NP-complete 问题。

图论建模

考虑单个条件 \(p_i\lor p_j\)，这意味这 \(\lnot p_i\Rightarrow p_j,\lnot p_j\Rightarrow p_i\)，即如果其中一个命题不成立，那么为保证条件成立，另一命题必须成立。

考虑按照这种“逻辑推理”的方式连有向边，那么如果存在路径使得 \(p_i\) 可达 \(\lnot p_i\)，则 \(p_i\) 一定不成立，更进一步说，如果 \(p_i\) 和 \(\lnot p_i\) 在同一强连通分量中，则一定没有合法解。

这个过程用 Tarjan 来实现。

对于其他形式的条件，也可以建出模型，主要就是一个若 A 则 B 的连边过程。

而如果钦定 \(p_i\) 一定成立，实际就是 \(\lnot p_i\) 一定不成立，因此连边 \(\lnot p_i\to p_i\) 即可。

由于命题与其逆否命题的真假性相同，我们若 A 则 B 的连边同样一定可以连出若非 B 则非 A 的连边。

求一组合法解

在判断有解基础上，我们得到一个 DAG，而如果 \(p_i\) 成立，其必要条件是 \(p_i\) 不可达 \(\lnot p_i\)，换言之如果 \(p_i\) 对应强连通分量的拓扑序在 \(\lnot p_i\) 之后，则 \(p_i\) 本身一定成立。

考虑证明这样单独考虑后全局也是合法的，设已知拓扑序有 \(t_{p_i}>t_{\lnot p_i},t_{p_j}>t_{\lnot p_j}\)，假设 \(p_i\) 可达 \(\lnot p_j\)，可知 \(t_{\lnot p_i}<t_{p_i}\le t_{\lnot p_i}\)，由连边的对称性得 \(p_j\) 同样可达 \(\lnot p_j\)，于是 \(t_{\lnot p_j}\le t_{p_j}<t_{\lnot p_i}\)，二者矛盾。故全局合法。

实际上不需要拓扑排序，因为我们本质是要知道是否可达，而如果存在强连通分量外的边 \((u,v)\)，而 \(v\) 先弹出，则 \(v\) 所在强连通分量的编号更小，相当于反向拓扑。所以只需要判断 \(p_i\) 强连通分量编号是否比 \(\lnot p_i\)，如果是则取 \(p_i\)，反之取 \(\lnot p_i\)。