 求解实现)
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载2-SAT二元可满足性是布尔可满足性问题SAT中每个子句恰好含两个文字的受限形式它避开了 SAT 的 NP 完全性可以在 O(nm) 时间内求解。本文以 cp-algorithms 仓库的 2-SAT 文档 为骨架完整讲解 2-CNF 公式如何转化为蕴含图、如何用强连通分量SCC判定可满足性并构造一组赋值同时结合仓库内TwoSatSolver的 C 实现与 test/test_2sat.cpp 测试用例给出可复制、可运行、可验证的完整解决方案。1. 什么是 2-SAT问题定义与复杂度边界SATBoolean satisfiability problem的核心任务是为布尔变量集合赋予真值使得给定的布尔公式为真。公式通常以CNF合取范式conjunctive normal form给出即多个子句clause的合取其中每个子句是一组文字literal即变量或其否定的析取。2-SAT2-satisfiability是 SAT 的一个受限版本每个子句恰好包含两个文字。例如下面就是一个典型的 2-SAT 问题——寻找 $a, b, c$ 的一组赋值使得以下公式为真$$(a \lor \lnot b) \land (\lnot a \lor b) \land (\lnot a \lor \lnot b) \land (a \lor \lnot c)$$关键在于复杂度差异一般 SAT 是NP 完全问题目前不存在已知的高效多项式时间算法而 2-SAT 可以在 $O(n m)$ 时间内高效求解其中 $n$ 是变量个数$m$ 是子句个数。这种仅把子句限制为两个文字所带来的复杂度巨变正是 2-SAT 在竞赛编程与工程约束求解中被广泛使用的原因。仓库中将其归类于图论Graph模块导航配置见 src/navigation.md与强连通分量、拓扑排序等图算法共享同一套方法论。2. 核心建模把 2-CNF 公式转化为蕴含图2-SAT 高效求解的第一步是将合取范式问题转化为一个带方向的图——蕴含图implication graph。2.1 蕴含范式implicative normal form注意这样一个逻辑等价关系表达式 $a \lor b$ 与以下两个蕴含式等价$$\lnot a \Rightarrow b \quad \text{且} \quad \lnot b \Rightarrow a$$直观理解如果两个变量中有一个为假那么另一个必须为真。也就是说每个含两个文字的子句 $(\ell_i \lor \ell_j)$ 都会贡献两条蕴含边$$\lnot \ell_i \Rightarrow \ell_j, \qquad \lnot \ell_j \Rightarrow \ell_i$$2.2 蕴含图的构造规则我们构造一个有向图来表示所有蕴含关系每个变量 $x$ 对应两个顶点$v_x$ 和 $v_{\lnot x}$即变量本身与它的否定每条边对应一条蕴含关系如 $a \Rightarrow b$ 从顶点 $a$ 连向顶点 $b$。仍以文档中的示例公式为例$$(a \lor \lnot b) \land (\lnot a \lor b) \land (\lnot a \lor \lnot b) \land (a \lor \lnot c)$$得到的蕴含图包含以下顶点与边来源子句蕴含边每条子句产生两条$a \lor \lnot b$$\lnot a \Rightarrow \lnot b$、$b \Rightarrow a$$\lnot a \lor b$$a \Rightarrow b$、$\lnot b \Rightarrow \lnot a$$\lnot a \lor \lnot b$$a \Rightarrow \lnot b$、$b \Rightarrow \lnot a$$a \lor \lnot c$$\lnot a \Rightarrow \lnot c$、$c \Rightarrow a$该示例的完整蕴含图如下2.3 蕴含图的关键性质蕴含图有两个对后续算法至关重要的性质对偶边性质若存在边 $a \Rightarrow b$则必然同时存在边 $\lnot b \Rightarrow \lnot a$逆否命题。这保证了图结构的对称性也是正确性证明中的核心工具。矛盾检测起点如果 $x$ 从 $\lnot x$ 可达且 $\lnot x$ 从 $x$ 可达那么无论给 $x$ 赋何值都会矛盾——赋 $x \text{true}$ 会推出 $\lnot x$ 也应为 $\text{true}$反之亦然。3. 可满足性判定强连通分量判据3.1 从可达到强连通分量图论中若顶点 $v$ 从顶点 $u$ 可达、且 $u$ 从 $v$ 可达则这两个顶点属于同一个强连通分量SCC。因此上面提到的矛盾条件可以翻译成图论语言2-SAT 问题存在解的充要条件是对任意变量 $x$顶点 $x$ 与顶点 $\lnot x$ 位于蕴含图的不同强连通分量中。这个条件不但是必要的而且是充分的充分性将在第 4 节的正确性证明中一并给出。由于求强连通分量可以在 $O(n m)$ 内完成整个可满足性判定也是线性复杂度。关于强连通分量的完整定义、Kosaraju 算法细节与凝结图condensation graph性质可参阅仓库中的 强连通分量文档。3.2 示例验证下图展示了示例公式蕴含图的全部强连通分量图中四个分量中没有一个同时包含某个变量 $x$ 及其否定 $\lnot x$例如 $a$ 与 $\lnot a$ 分属不同分量因此该公式可满足。仅作演示一组满足赋值为 $a \text{false}$、$b \text{false}$、$c \text{false}$赋值构造的具体算法见下一节。4. 构造赋值SCC 拓扑序与赋值规则即便解存在蕴含图中也可能出现 $\lnot x$ 从 $x$ 可达的情况或反之但不会同时双向可达否则就落入上一节的不可满足情形。此时给 $x$ 赋其中一个值会导出矛盾赋另一个值则不会。问题转化为如何为每个变量选择不会制造矛盾的值。4.1 拓扑序赋值规则算法按如下方式给每个变量赋值将强连通分量按拓扑序排序即若存在从 $v$ 到 $u$ 的路径则 $\text{comp}[v] \le \text{comp}[u]$记 $\text{comp}[v]$ 为顶点 $v$ 所属分量的序号若 $\text{comp}[x] \text{comp}[\lnot x]$则给 $x$ 赋 $\text{false}$否则赋 $\text{true}$。直观理解拓扑序越靠后的分量在赋值时覆盖越靠前的分量把 $x$ 取为分量序号更靠后的一方可使蕴含链顺着拓扑方向传播而不会反向产生矛盾。4.2 正确性证明设 $x$ 被赋为 $\text{true}$另一情形对称可证需证明不会导出矛盾第一步$x$ 无法到达 $\lnot x$。因为 $x$ 被赋 $\text{true}$必有 $\text{comp}[x] \text{comp}[\lnot x]$即 $\lnot x$ 所在分量位于 $x$ 所在分量的左侧拓扑序更靠前从拓扑序靠后的分量自然无法到达靠前的分量。第二步不存在变量 $y$ 使 $y$ 与 $\lnot y$ 都从 $x$ 可达。若存在则 $x \text{true}$ 会同时推出 $y \text{true}$ 和 $\lnot y \text{true}$构成矛盾。用反证法假设 $y$ 与 $\lnot y$ 都从 $x$ 可达则由蕴含图的对偶边性质$\lnot x$ 同时从 $y$ 和 $\lnot y$ 可达根据传递性$\lnot x$ 从 $x$ 可达这与第一步矛盾。因此该赋值规则在任意变量与其否定在不同 SCC的假设下必然产生一组无矛盾的解同时反证了第 3 节的可满足性判据。5. 完整实现TwoSatSolverKosaraju 线性赋值5.1 算法整体流程实现分为两阶段构图 求 SCC构造蕴含图后用Kosaraju 算法在 $O(n m)$ 内找出全部强连通分量。Kosaraju 的第二轮遍历恰好按拓扑序访问各分量因此能方便地为每个顶点算出 $\text{comp}[v]$。赋值对每个变量 $x$比较 $\text{comp}[x]$ 与 $\text{comp}[\lnot x]$。若二者相等说明 $x$ 与其否定在同一分量直接返回false表示该 2-SAT 实例不可满足否则按第 4 节的规则写入赋值。顶点编号约定索引 $2k$ 与 $2k1$ 分别对应变量 $k$ 与其否定$2k1$ 对应否定。5.2 核心代码以下是仓库文档给出的完整实现对已构造好的蕴含图adj及其转置图 $adj^{\intercal}$ 工作转置图每条边方向取反struct TwoSatSolver { int n_vars; int n_vertices; vectorvectorint adj, adj_t; vectorbool used; vectorint order, comp; vectorbool assignment; TwoSatSolver(int _n_vars) : n_vars(_n_vars), n_vertices(2 * n_vars), adj(n_vertices), adj_t(n_vertices), used(n_vertices), order(), comp(n_vertices, -1), assignment(n_vars) { order.reserve(n_vertices); } void dfs1(int v) { used[v] true; for (int u : adj[v]) { if (!used[u]) dfs1(u); } order.push_back(v); } void dfs2(int v, int cl) { comp[v] cl; for (int u : adj_t[v]) { if (comp[u] -1) dfs2(u, cl); } } bool solve_2SAT() { order.clear(); used.assign(n_vertices, false); for (int i 0; i n_vertices; i) { if (!used[i]) dfs1(i); } comp.assign(n_vertices, -1); for (int i 0, j 0; i n_vertices; i) { int v order[n_vertices - i - 1]; if (comp[v] -1) dfs2(v, j); } assignment.assign(n_vars, false); for (int i 0; i n_vertices; i 2) { if (comp[i] comp[i 1]) return false; assignment[i / 2] comp[i] comp[i 1]; } return true; } void add_disjunction(int a, bool na, int b, bool nb) { // na and nb signify whether a and b are to be negated a 2 * a ^ na; b 2 * b ^ nb; int neg_a a ^ 1; int neg_b b ^ 1; adj[neg_a].push_back(b); adj[neg_b].push_back(a); adj_t[b].push_back(neg_a); adj_t[a].push_back(neg_b); } static void example_usage() { TwoSatSolver solver(3); // a, b, c solver.add_disjunction(0, false, 1, true); // a v not b solver.add_disjunction(0, true, 1, true); // not a v not b solver.add_disjunction(1, false, 2, false); // b v c solver.add_disjunction(0, false, 0, false); // a v a assert(solver.solve_2SAT() true); auto expected vectorbool{{true, false, true}}; assert(solver.assignment expected); } };5.3 实现细节解读add_disjunction(a, na, b, nb)添加子句 $(a^{na} \lor b^{nb})$其中na/nb为真表示对应文字取否定。通过位运算2 * a ^ na完成顶点编号与正负性的统一编码^ 1即翻转否定标志一条子句同时向原图与转置图写入两条对偶蕴含边构图与求解可分离进行。dfs1Kosaraju 第一轮按完成时间记录顶点顺序到order。dfs2Kosaraju 第二轮在转置图上按order逆序遍历每轮 DFS 划出一个新的 SCC编号由cl递增给出。solve_2SAT中的赋值行assignment[i / 2] comp[i] comp[i 1];正好对应第 4 节的规则——若 $\text{comp}[x] \text{comp}[\lnot x]$ 则赋 $\text{true}$否则赋 $\text{false}$。由于 Kosaraju 第二轮的遍历顺序天然满足拓扑序要求这里直接比较分量编号即可无需额外排序。6. 仓库源码佐证测试流水线与工程实践6.1 测试框架如何复用本文代码仓库采用从 Markdown 提取代码块再编译测试的流水线test/extract_snippets.py 会扫描src/下所有.md文档用正则匹配{.cpp fileNAME}开头的代码块将其内容写出为NAME.h头文件本实例对应2sat.h随后 test/test.sh 用g -stdc17默认编译器可用CXX环境变量覆盖编译test/下的全部*.cpp测试并逐个运行断言。6.2 测试用例覆盖了哪些场景test/test_2sat.cpp 共包含四个测试函数从不同角度验证求解器test_2sat_example_usage()直接调用TwoSatSolver::example_usage()验证文档中的内嵌示例含单变量子句 $a \lor a$得到{true, false, true}test_2sat_article_example()复现本文开头公式 $(a \lor \lnot b) \land (\lnot a \lor b) \land (\lnot a \lor \lnot b) \land (a \lor \lnot c)$断言可满足且赋值为{false, false, false}——与文档第 3.2 节演示的解完全一致test_2sat_unsatisfiable()对两个变量添加全部四种子句组合 $a \lor b$、$a \lor \lnot b$、$\lnot a \lor b$、$\lnot a \lor \lnot b$等价于 $a$ 与 $\lnot a$ 落入同一 SCCsolve_2SAT()必须返回false覆盖了不可满足分支test_2sat_other_satisfiable_example()构造一个存在多组解的实例4 个变量断言返回的解落在两个合法解{true,true,false,true}或{true,false,false,true}之一验证了存在解但解不唯一时的正确性。这些用例共同验证了可满足/不可满足判定、单变量退化子句、多解场景以及文档示例的逐字复现均可通过仓库中的test.sh一键编译运行。7. 复杂度分析与适用边界时间复杂度$O(n m)$——两次 DFSKosaraju线性遍历原图与转置图加上一轮线性赋值其中 $n$ 为变量数、$m$ 为子句数蕴含图顶点数为 $2n$边数为 $2m$空间复杂度$O(n m)$主要存储原图、转置图及 DFS 辅助数组适用边界算法针对的是每个子句恰好两个文字的 2-CNF 公式。若存在含 3 个及以上文字的子句3-SAT问题重新落入 NP 完全范畴本方法不再适用。此外代码默认使用vector邻接表与递归 DFS对极深图需注意递归栈深度。8. 练习题目为巩固对 2-SAT 建模与求解的理解文档在末尾附带了以下经典练习题按原文档清单收录Codeforces: The Door Problem开关与门约束建模Kattis: Illumination照明约束问题UVA: Rectangles矩形约束判定Codeforces: Radio Stations广播站频率互斥约束CSES: Giant Pizza经典 2-SAT 入门题Codeforces: -1三分支符号约束Gym: Colorful Village村庄染色约束POI: Renovation翻新规划约束练习时建议先独立把题目约束写成 2-CNF 子句再通过add_disjunction喂给TwoSatSolver验证建模是否正确。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐cp-algorithms 无向图连通分量查找DFS/BFS 双实现与 O(nm) 复杂度剖析cp algorithms 无向图连通分量查找DFS/BFS 双实现与 O nm 复杂度剖析 无向图中所有连通分量的查找是图论最基础的遍历问题之一给定 n文档教程知识库workerd 官方类型包 cloudflare/workers-types安装配置、Bindings 类型声明与 JSG RTTI 生成原理workerd 官方类型包 cloudflare/workers types安装配置、Bindings 类型声明与 JSG RTTI 生成原理 本篇技术指南文档教程知识库前端 ID 唯一性实战指南基于 Front-End-Checklist 的 unique-id 规则深度解析前端 ID 唯一性实战指南基于 Front End Checklist 的 unique id 规则深度解析 本文以 Front End Checklist文档教程知识库上一篇x64dbg 插件回调 PLUG_CB_PAUSEDEBUG 详解调试器暂停事件的注册、触发时机与实战用法下一篇终极指南五步让老旧Mac焕然新生免费安装最新macOS系统创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 cp-algorithms 2-SAT 全解：蕴含图建模、强连通分量判定与 O(n+m) 求解实现
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载2-SAT二元可满足性是布尔可满足性问题SAT中每个子句恰好含两个文字的受限形式它避开了 SAT 的 NP 完全性可以在 O(nm) 时间内求解。本文以 cp-algorithms 仓库的 2-SAT 文档 为骨架完整讲解 2-CNF 公式如何转化为蕴含图、如何用强连通分量SCC判定可满足性并构造一组赋值同时结合仓库内TwoSatSolver的 C 实现与 test/test_2sat.cpp 测试用例给出可复制、可运行、可验证的完整解决方案。1. 什么是 2-SAT问题定义与复杂度边界SATBoolean satisfiability problem的核心任务是为布尔变量集合赋予真值使得给定的布尔公式为真。公式通常以CNF合取范式conjunctive normal form给出即多个子句clause的合取其中每个子句是一组文字literal即变量或其否定的析取。2-SAT2-satisfiability是 SAT 的一个受限版本每个子句恰好包含两个文字。例如下面就是一个典型的 2-SAT 问题——寻找 $a, b, c$ 的一组赋值使得以下公式为真$$(a \lor \lnot b) \land (\lnot a \lor b) \land (\lnot a \lor \lnot b) \land (a \lor \lnot c)$$关键在于复杂度差异一般 SAT 是NP 完全问题目前不存在已知的高效多项式时间算法而 2-SAT 可以在 $O(n m)$ 时间内高效求解其中 $n$ 是变量个数$m$ 是子句个数。这种仅把子句限制为两个文字所带来的复杂度巨变正是 2-SAT 在竞赛编程与工程约束求解中被广泛使用的原因。仓库中将其归类于图论Graph模块导航配置见 src/navigation.md与强连通分量、拓扑排序等图算法共享同一套方法论。2. 核心建模把 2-CNF 公式转化为蕴含图2-SAT 高效求解的第一步是将合取范式问题转化为一个带方向的图——蕴含图implication graph。2.1 蕴含范式implicative normal form注意这样一个逻辑等价关系表达式 $a \lor b$ 与以下两个蕴含式等价$$\lnot a \Rightarrow b \quad \text{且} \quad \lnot b \Rightarrow a$$直观理解如果两个变量中有一个为假那么另一个必须为真。也就是说每个含两个文字的子句 $(\ell_i \lor \ell_j)$ 都会贡献两条蕴含边$$\lnot \ell_i \Rightarrow \ell_j, \qquad \lnot \ell_j \Rightarrow \ell_i$$2.2 蕴含图的构造规则我们构造一个有向图来表示所有蕴含关系每个变量 $x$ 对应两个顶点$v_x$ 和 $v_{\lnot x}$即变量本身与它的否定每条边对应一条蕴含关系如 $a \Rightarrow b$ 从顶点 $a$ 连向顶点 $b$。仍以文档中的示例公式为例$$(a \lor \lnot b) \land (\lnot a \lor b) \land (\lnot a \lor \lnot b) \land (a \lor \lnot c)$$得到的蕴含图包含以下顶点与边来源子句蕴含边每条子句产生两条$a \lor \lnot b$$\lnot a \Rightarrow \lnot b$、$b \Rightarrow a$$\lnot a \lor b$$a \Rightarrow b$、$\lnot b \Rightarrow \lnot a$$\lnot a \lor \lnot b$$a \Rightarrow \lnot b$、$b \Rightarrow \lnot a$$a \lor \lnot c$$\lnot a \Rightarrow \lnot c$、$c \Rightarrow a$该示例的完整蕴含图如下2.3 蕴含图的关键性质蕴含图有两个对后续算法至关重要的性质对偶边性质若存在边 $a \Rightarrow b$则必然同时存在边 $\lnot b \Rightarrow \lnot a$逆否命题。这保证了图结构的对称性也是正确性证明中的核心工具。矛盾检测起点如果 $x$ 从 $\lnot x$ 可达且 $\lnot x$ 从 $x$ 可达那么无论给 $x$ 赋何值都会矛盾——赋 $x \text{true}$ 会推出 $\lnot x$ 也应为 $\text{true}$反之亦然。3. 可满足性判定强连通分量判据3.1 从可达到强连通分量图论中若顶点 $v$ 从顶点 $u$ 可达、且 $u$ 从 $v$ 可达则这两个顶点属于同一个强连通分量SCC。因此上面提到的矛盾条件可以翻译成图论语言2-SAT 问题存在解的充要条件是对任意变量 $x$顶点 $x$ 与顶点 $\lnot x$ 位于蕴含图的不同强连通分量中。这个条件不但是必要的而且是充分的充分性将在第 4 节的正确性证明中一并给出。由于求强连通分量可以在 $O(n m)$ 内完成整个可满足性判定也是线性复杂度。关于强连通分量的完整定义、Kosaraju 算法细节与凝结图condensation graph性质可参阅仓库中的 强连通分量文档。3.2 示例验证下图展示了示例公式蕴含图的全部强连通分量图中四个分量中没有一个同时包含某个变量 $x$ 及其否定 $\lnot x$例如 $a$ 与 $\lnot a$ 分属不同分量因此该公式可满足。仅作演示一组满足赋值为 $a \text{false}$、$b \text{false}$、$c \text{false}$赋值构造的具体算法见下一节。4. 构造赋值SCC 拓扑序与赋值规则即便解存在蕴含图中也可能出现 $\lnot x$ 从 $x$ 可达的情况或反之但不会同时双向可达否则就落入上一节的不可满足情形。此时给 $x$ 赋其中一个值会导出矛盾赋另一个值则不会。问题转化为如何为每个变量选择不会制造矛盾的值。4.1 拓扑序赋值规则算法按如下方式给每个变量赋值将强连通分量按拓扑序排序即若存在从 $v$ 到 $u$ 的路径则 $\text{comp}[v] \le \text{comp}[u]$记 $\text{comp}[v]$ 为顶点 $v$ 所属分量的序号若 $\text{comp}[x] \text{comp}[\lnot x]$则给 $x$ 赋 $\text{false}$否则赋 $\text{true}$。直观理解拓扑序越靠后的分量在赋值时覆盖越靠前的分量把 $x$ 取为分量序号更靠后的一方可使蕴含链顺着拓扑方向传播而不会反向产生矛盾。4.2 正确性证明设 $x$ 被赋为 $\text{true}$另一情形对称可证需证明不会导出矛盾第一步$x$ 无法到达 $\lnot x$。因为 $x$ 被赋 $\text{true}$必有 $\text{comp}[x] \text{comp}[\lnot x]$即 $\lnot x$ 所在分量位于 $x$ 所在分量的左侧拓扑序更靠前从拓扑序靠后的分量自然无法到达靠前的分量。第二步不存在变量 $y$ 使 $y$ 与 $\lnot y$ 都从 $x$ 可达。若存在则 $x \text{true}$ 会同时推出 $y \text{true}$ 和 $\lnot y \text{true}$构成矛盾。用反证法假设 $y$ 与 $\lnot y$ 都从 $x$ 可达则由蕴含图的对偶边性质$\lnot x$ 同时从 $y$ 和 $\lnot y$ 可达根据传递性$\lnot x$ 从 $x$ 可达这与第一步矛盾。因此该赋值规则在任意变量与其否定在不同 SCC的假设下必然产生一组无矛盾的解同时反证了第 3 节的可满足性判据。5. 完整实现TwoSatSolverKosaraju 线性赋值5.1 算法整体流程实现分为两阶段构图 求 SCC构造蕴含图后用Kosaraju 算法在 $O(n m)$ 内找出全部强连通分量。Kosaraju 的第二轮遍历恰好按拓扑序访问各分量因此能方便地为每个顶点算出 $\text{comp}[v]$。赋值对每个变量 $x$比较 $\text{comp}[x]$ 与 $\text{comp}[\lnot x]$。若二者相等说明 $x$ 与其否定在同一分量直接返回false表示该 2-SAT 实例不可满足否则按第 4 节的规则写入赋值。顶点编号约定索引 $2k$ 与 $2k1$ 分别对应变量 $k$ 与其否定$2k1$ 对应否定。5.2 核心代码以下是仓库文档给出的完整实现对已构造好的蕴含图adj及其转置图 $adj^{\intercal}$ 工作转置图每条边方向取反struct TwoSatSolver { int n_vars; int n_vertices; vectorvectorint adj, adj_t; vectorbool used; vectorint order, comp; vectorbool assignment; TwoSatSolver(int _n_vars) : n_vars(_n_vars), n_vertices(2 * n_vars), adj(n_vertices), adj_t(n_vertices), used(n_vertices), order(), comp(n_vertices, -1), assignment(n_vars) { order.reserve(n_vertices); } void dfs1(int v) { used[v] true; for (int u : adj[v]) { if (!used[u]) dfs1(u); } order.push_back(v); } void dfs2(int v, int cl) { comp[v] cl; for (int u : adj_t[v]) { if (comp[u] -1) dfs2(u, cl); } } bool solve_2SAT() { order.clear(); used.assign(n_vertices, false); for (int i 0; i n_vertices; i) { if (!used[i]) dfs1(i); } comp.assign(n_vertices, -1); for (int i 0, j 0; i n_vertices; i) { int v order[n_vertices - i - 1]; if (comp[v] -1) dfs2(v, j); } assignment.assign(n_vars, false); for (int i 0; i n_vertices; i 2) { if (comp[i] comp[i 1]) return false; assignment[i / 2] comp[i] comp[i 1]; } return true; } void add_disjunction(int a, bool na, int b, bool nb) { // na and nb signify whether a and b are to be negated a 2 * a ^ na; b 2 * b ^ nb; int neg_a a ^ 1; int neg_b b ^ 1; adj[neg_a].push_back(b); adj[neg_b].push_back(a); adj_t[b].push_back(neg_a); adj_t[a].push_back(neg_b); } static void example_usage() { TwoSatSolver solver(3); // a, b, c solver.add_disjunction(0, false, 1, true); // a v not b solver.add_disjunction(0, true, 1, true); // not a v not b solver.add_disjunction(1, false, 2, false); // b v c solver.add_disjunction(0, false, 0, false); // a v a assert(solver.solve_2SAT() true); auto expected vectorbool{{true, false, true}}; assert(solver.assignment expected); } };5.3 实现细节解读add_disjunction(a, na, b, nb)添加子句 $(a^{na} \lor b^{nb})$其中na/nb为真表示对应文字取否定。通过位运算2 * a ^ na完成顶点编号与正负性的统一编码^ 1即翻转否定标志一条子句同时向原图与转置图写入两条对偶蕴含边构图与求解可分离进行。dfs1Kosaraju 第一轮按完成时间记录顶点顺序到order。dfs2Kosaraju 第二轮在转置图上按order逆序遍历每轮 DFS 划出一个新的 SCC编号由cl递增给出。solve_2SAT中的赋值行assignment[i / 2] comp[i] comp[i 1];正好对应第 4 节的规则——若 $\text{comp}[x] \text{comp}[\lnot x]$ 则赋 $\text{true}$否则赋 $\text{false}$。由于 Kosaraju 第二轮的遍历顺序天然满足拓扑序要求这里直接比较分量编号即可无需额外排序。6. 仓库源码佐证测试流水线与工程实践6.1 测试框架如何复用本文代码仓库采用从 Markdown 提取代码块再编译测试的流水线test/extract_snippets.py 会扫描src/下所有.md文档用正则匹配{.cpp fileNAME}开头的代码块将其内容写出为NAME.h头文件本实例对应2sat.h随后 test/test.sh 用g -stdc17默认编译器可用CXX环境变量覆盖编译test/下的全部*.cpp测试并逐个运行断言。6.2 测试用例覆盖了哪些场景test/test_2sat.cpp 共包含四个测试函数从不同角度验证求解器test_2sat_example_usage()直接调用TwoSatSolver::example_usage()验证文档中的内嵌示例含单变量子句 $a \lor a$得到{true, false, true}test_2sat_article_example()复现本文开头公式 $(a \lor \lnot b) \land (\lnot a \lor b) \land (\lnot a \lor \lnot b) \land (a \lor \lnot c)$断言可满足且赋值为{false, false, false}——与文档第 3.2 节演示的解完全一致test_2sat_unsatisfiable()对两个变量添加全部四种子句组合 $a \lor b$、$a \lor \lnot b$、$\lnot a \lor b$、$\lnot a \lor \lnot b$等价于 $a$ 与 $\lnot a$ 落入同一 SCCsolve_2SAT()必须返回false覆盖了不可满足分支test_2sat_other_satisfiable_example()构造一个存在多组解的实例4 个变量断言返回的解落在两个合法解{true,true,false,true}或{true,false,false,true}之一验证了存在解但解不唯一时的正确性。这些用例共同验证了可满足/不可满足判定、单变量退化子句、多解场景以及文档示例的逐字复现均可通过仓库中的test.sh一键编译运行。7. 复杂度分析与适用边界时间复杂度$O(n m)$——两次 DFSKosaraju线性遍历原图与转置图加上一轮线性赋值其中 $n$ 为变量数、$m$ 为子句数蕴含图顶点数为 $2n$边数为 $2m$空间复杂度$O(n m)$主要存储原图、转置图及 DFS 辅助数组适用边界算法针对的是每个子句恰好两个文字的 2-CNF 公式。若存在含 3 个及以上文字的子句3-SAT问题重新落入 NP 完全范畴本方法不再适用。此外代码默认使用vector邻接表与递归 DFS对极深图需注意递归栈深度。8. 练习题目为巩固对 2-SAT 建模与求解的理解文档在末尾附带了以下经典练习题按原文档清单收录Codeforces: The Door Problem开关与门约束建模Kattis: Illumination照明约束问题UVA: Rectangles矩形约束判定Codeforces: Radio Stations广播站频率互斥约束CSES: Giant Pizza经典 2-SAT 入门题Codeforces: -1三分支符号约束Gym: Colorful Village村庄染色约束POI: Renovation翻新规划约束练习时建议先独立把题目约束写成 2-CNF 子句再通过add_disjunction喂给TwoSatSolver验证建模是否正确。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐cp-algorithms 无向图连通分量查找DFS/BFS 双实现与 O(nm) 复杂度剖析cp algorithms 无向图连通分量查找DFS/BFS 双实现与 O nm 复杂度剖析 无向图中所有连通分量的查找是图论最基础的遍历问题之一给定 n文档教程知识库workerd 官方类型包 cloudflare/workers-types安装配置、Bindings 类型声明与 JSG RTTI 生成原理workerd 官方类型包 cloudflare/workers types安装配置、Bindings 类型声明与 JSG RTTI 生成原理 本篇技术指南文档教程知识库前端 ID 唯一性实战指南基于 Front-End-Checklist 的 unique-id 规则深度解析前端 ID 唯一性实战指南基于 Front End Checklist 的 unique id 规则深度解析 本文以 Front End Checklist文档教程知识库上一篇x64dbg 插件回调 PLUG_CB_PAUSEDEBUG 详解调试器暂停事件的注册、触发时机与实战用法下一篇终极指南五步让老旧Mac焕然新生免费安装最新macOS系统创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考