【图论】2-SAT问题

2-SAT问题

定义

每句话包含两个条件，真/假，用或连接

许多话以且连接

求一组真假赋值使其符合所有要求

分析

每个原子拆成真/假两个点（离散数学的方法，真值表也可推）：

原式	建图
$\neg a\vee b$	$a\rightarrow b\wedge\neg b\rightarrow\neg a$
$a \vee b$	$\neg a\rightarrow b\wedge\neg b\rightarrow a$
$\neg a\vee\neg b$	$a\rightarrow\neg b\wedge b\rightarrow\neg a$

同一强连通分量中的点取值相同，对于一个原子的真假点，取拓扑序在后的。

如果真假点在一个强连通分量中就没有符合条件的数据。

可以直接利用tarjan缩点出来的scc数组，本身就是拓扑逆序。