题解：P4782 【模板】2-SAT
zhouwenbo1234
·
·
题解
P4782 【模板】2-SAT
怎么求2--SAT?
因为一个节点只有两个状态（真或假），那我们就可以拆点，将一个节点拆成两个点（两排），上面一排全是假，下面一排全是真。
然后根据题意可以知道如果 X_j ≠ b 为真，那么 X_i = a，反之同理，由假推真。
证明
因为他要至少满足一个条件。
### 建图
那我们就可以开始建边了，将 $X_i$ 为真的状态的边连到 $X_j$ 为假的状态的编号上，再从 $X_j$ 以同样的方式连到 $X_i$ 上，这样建边就完成了。
然后 tarjan 就比较板子了，~~自己 c 之前的代码~~。
### 判解
我们只需要判断有没有某个节点的为假和为真的编号在强连通分量里相等就行了，举个例子你就懂了：$X_1 = 1$ 或 $X_2 = 1$ 和 $X_1 = 1$ 或 $X_2 = 0$ 这个就是矛盾的，如果 $X_1 ≠ 1$，那么一定有 $X_2 = 1$，但当 $X_2 = 1$ 而 $≠ 0$ 时，就会触发第二个条件一定有 $X_1 = 1$，这样就矛盾了。
### 细节
输出方案时要输出编号小的，因为拓扑排序是小编号有较大的拓扑序，由于它又依赖于其他节点，为避免后效性矛盾，所以要选择较大的拓扑序也就是较小的序号。
### 代码
接下来奉上我的代码，有点丑，还请见谅。
```
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m,head[N],cnt=-1;
int dfn[N],low[N],col[N],idx,tot;
//dfn表示dfs访问顺序，low表示能回溯到的最早节点，col表示强连通分量的编号，idx表示时间戳
//tot表示强连通分量的计数
bool in[N];//节点数否在栈中
stack <int> stk;
struct node{
int u,v,next;
}e[N*4];
int read(){
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
void adde(int u,int v){
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void tarjan(int u){
dfn[u]=low[u]=++idx;
stk.push(u);
in[u]=true;
for (int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
if (!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (in[v])
low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u]){
tot++;
int v;
while (1){
v=stk.top();
stk.pop();
in[v]=false;
col[v]=tot;
if (v==u)
break;
}
}
}
int main(){
memset(head,-1,sizeof head);
n=read(),m=read();
for (int i=1;i<=m;i++){
int x=read(),a=read(),y=read(),b=read();
int u=(x<<1)|(a^1);//x!=a的状态
int v=(y<<1)|b;//y==b的状态
adde(u,v);
u=(x<<1)|a;//x==a的状态
v=(y<<1)|(b^1);//y!=b的状态
//因为如果a的状态不满足的话，那么b的状态一定满足，反向同理
adde(v,u);
}
for (int i=2;i<=(n<<1|1);i++)
if (!dfn[i])
tarjan(i);
for (int i=1;i<=n;i++){
int f_node=i<<1;//x为假的节点
int t_node=i<<1|1;//x为真的节点
if (col[f_node]==col[t_node]){
//如果这个节点又为假又为真，那么就矛盾
//比如 x1=1 或 x1=0 就是矛盾的
cout <<"IMPOSSIBLE"<<endl;
return 0;
}
}
cout <<"POSSIBLE"<<endl;
for (int i=1;i<=n;i++){
int f_node=i<<1;//同上
int t_node=i<<1|1;
if (col[f_node]<col[t_node])
//拓扑排序是小序号有较大的拓扑序，大序号反之，为了避免后效性，所以选择较大的拓扑序也就是较小的序号
cout <<0<<" ";
else
cout <<1<<" ";
}
cout <<endl;
return 0;
}
```