2-SAT问题指的是对于若干限制求出一组可行解的问题。

考虑对于$n$个值域为${0,1}$的变量$x_1 , x_2 ,...,x_n$ 满足若干限制：

若 $x_i = p$ 则 $x_j = q ( i,j\in[1,n],p,q \in \{0,1\})$

我们考虑对于每一个变量$x_i$开一个值域$x_{i,0} , x_{i,1}$表示第$i$个变量取值为$0/1$的点。

然后考虑每一组命题， 若 $x_i = p$ 则 $x_j = q , i,j\in[1,n],p,q \in \{0,1\}$ ，

首先把$x_{i,p}$和$x_{j,q}$两个点连一条单向边。

并且 由于这个命题非常特殊，值域大小只为2 ， 其逆否命题也是限制（可以显然的反证）。

于是就把$x_{j,1-q}$和$x_{i,1-p}$ 连一条单向边。

 

然后对于上面的图跑tarjan找出scc，如果$x_{i,0}$和$x_{i,1}$在同一连通块中了，

说明下列命题成立： “若$x_i = 0$则$x_i = 1$ ” ，“若$x_i = 1$则$x_i = 0$ ” 所以此时答案无解。

 

如何构造出一组解呢，由于tarjan的dfs特性，

设$c_i$表示通过tarjan算法求出的连通块编号（这本身就是逆拓扑序的）。

$val_i = c_{x_{i,0}} > c_{x_{i,1}}$  就构造出$val_i , i\in [1,n]$一组合法解了。