核心判断：拆点建图后跑Tarjan，若任意变量i与其反变量i+n（或2i-1与2i）在同一个强连通分量中，则无解，因导致i为真⇔i为假的逻辑矛盾；检查所有i∈[1,n]是否满足sccno[2i-1]≠sccno[2i]，任一相等即无解。
怎么用Tarjan判断2-SAT是否有解
核心就一条：拆点建图后跑Tarjan，若任意变量 i 与其反变量 i + n（或 2*i-1 和 2*i）在同一个强连通分量里，则无解。
原因在于——i → i + n 表示“选 i 就必须选 i + n”，而强连通意味着两者可互相推出，即 i 为真 ⇒ i 为假，逻辑矛盾。
实际编码中注意两点：
- 变量编号从
1开始时，常用2*i-1表示x_i = true，2*i表示x_i = false；也有实现用i和i+n，但必须统一，否则sccno[i] == sccno[i+n]判断失效 - Tarjan结束后，检查所有
i ∈ [1, n]是否满足sccno[2*i-1] != sccno[2*i]；只要有一对相等，直接输出"IMPOSSIBLE"
建图时连边规则容易错在哪
每条约束“x 为 a 或 y 为 b”（a,b ∈ {0,1}）必须转成两条蕴含边，漏掉一条就会漏约束。
立即学习“C++免费学习笔记（深入）”；
例如：“x = 1 或 y = 0” 等价于：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 若
x = 0，则必有y = 0→ 连边2*x→2*y（x=false→y=false） - 若
y = 1，则必有x = 1→ 连边2*y-1→2*x-1（y=true→x=true）
常见错误：
- 把“或”条件只连一条边，导致图不完整，SCC结果不可靠
- 混淆真假节点编号，比如把
x=true写成2*x，而x=false写成2*x-1，和主流约定相反，后续sccno比较会全错 - 输入中
a、b是 0/1，但没做映射转换，直接当索引用，造成数组越界或连错边
为什么缩点后比较 sccno 大小就能构造解
不是靠拓扑排序，而是靠 Tarjan 的染色顺序隐含了逆拓扑序：编号越小的 SCC，在 DAG 中越靠近叶子（出度更可能为 0）；编号越大的 SCC 越靠近源点。
因此对每个变量 i，我们选 sccno[2*i-1] 对应的取值（即选编号小的那个节点所代表的真假态），能保证不会触发任何蕴含边的冲突。
关键细节：
- 这个策略成立的前提是 Tarjan 实现中
col（或sccno）按出栈顺序递增赋值，即先完成的 SCC 编号更小 —— 多数标准实现都如此，但需确认你用的 Tarjan 是否满足 - 如果用了非标准 Tarjan（如按入栈顺序编号），则必须显式缩点+拓扑排序再选“出度为 0”的 SCC，不能直接比
sccno - 输出解时，不要写
if (sccno[i] 这类代码，除非你明确定义了 <code>i+n是反变量；更安全的是固定用2*i-1/2*i并严格对应
C++ 实现中几个隐蔽的坑
模板代码看着短，但线上跑挂往往卡在边界和初始化上：
-
dfn[]和low[]数组必须清零，否则多测时残留值导致 Tarjan 提前退出 - 图的总点数是
2*n，邻接表大小、dfn数组长度、栈空间都要按2*n+10分配，别只开n - 使用
vector存图时，每次多测前要调用for(int i=0; i，否则旧边残留 - 输入变量下标常从 1 开始，但有人误用 0-indexed 建边，导致
2*0-1 = -1访问非法内存
最麻烦的是：当 n 很大（如 1e6）、m 接近 2e6 时，递归版 Tarjan 容易爆栈，必须改用手动栈或 BFS 式迭代 DFS，这点文档很少提，但线上 OJ 经常因此 RE。
