三公算账机器人 2-SAT 算法
结合你之前关注的图论最短路径、拓扑排序相关算法题解需求,以及面向学员做算法教学的场景,2-SAT是布尔可满足性问题中k=2的特殊分支,也是图论强连通缩点的经典应用,能在O(n+m)线性时间内求解所有子句最多包含2个布尔变量的约束满足问题,是算法竞赛、工程约束场景中非常实用的图论工具。核心基础概念2-SAT问题的标准形式是:给定n个布尔变量,同时给出m个形如“a∨b”的约束子句,要求为所有变量赋值,让所有子句同时成立。每个布尔变量xi会被拆成两个互斥的节点:xi为真、xi为假,n个变量总共对应2n个图节点。每一条“a∨b”的约束子句,本质等价于两条逻辑推理规则:如果a不成立则b必须成立,如果b不...