【模板】2-SAT

【模板】2-SAT 问题

题目描述

有 $n$ 个布尔变量 $x_1$$\sim$$x_n$，另有 $m$ 个需要满足的条件，每个条件的形式都是 「$x_i$ 为 true / false 或 $x_j$ 为 true / false」。比如 「$x_1$ 为真或 $x_3$ 为假」、「$x_7$ 为假或 $x_2$ 为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

输入格式

第一行两个整数 $n$ 和 $m$，意义如题面所述。

接下来 $m$ 行每行 $4$ 个整数 $i$, $a$, $j$, $b$，表示 「$x_i$ 为 $a$ 或 $x_j$ 为 $b$」( a , b ∈ { 0 , 1 } a, b\in \{0,1\} a,b∈{0,1})

输出格式

如无解，输出 IMPOSSIBLE；否则输出 POSSIBLE。

下一行 $n$ 个整数 $x_1\sim x_n$（ x i ∈ { 0 , 1 } x_i\in\{0,1\} xi​∈{0,1}），表示构造出的解。

样例 #1

样例输入 #1

3 1
1 1 3 0
1
2

样例输出 #1

POSSIBLE
0 0 0
1
2

提示

$1\le n,m\le 10^6$ , 前 $3$ 个点卡小错误，后面 $5$ 个点卡效率。

由于数据随机生成，可能会含有（ 10 0 10 0）之类的坑，但按照最常规写法的写的标程没有出错，各个数据点卡什么的提示在标程里。

思路

对于一个$aorb$的表达式，我们可以拆成$(!aandb)or(!banda)or(aandb)$
我们可以建图$!a\to b$和$!b\to a$表示选了$!a$就得选$b$，反之亦然。

习惯上，我们给缩点后的图排一个拓扑序，当 $x$ 所在强连通分量的拓扑序在 $!x$ 所在的强连通分量的拓扑序之后的话我们就给 $x$ 取真。

这题tarjan缩完点就已经有个顺序了，不过这是反着的拓扑序，所以比较关系是反着的。

#include
#define int long long
using namespace std;
const int N=2e6+77;
int dfn[N],low[N],b[N],s[N],c[N],ls[N],cnt,id,top,tot;
struct E
{
	int to,next;
}e[N<<1];
void add(int u,int v)
{
	e[++cnt].to=v; e[cnt].next=ls[u]; ls[u]=cnt;
}
void tarjan(int u)
{
	dfn[u]=low[u]=++tot; b[u]=1;
	s[++top]=u; 
	for(int i=ls[u]; i; i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(b[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		id++;
		while(s[top+1]!=u)
		{
			c[s[top]]=id;
			b[s[top]]=0; top--;
		}
	}
}
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=m; i++)
	{
		int x,y,a,b;
		cin>>x>>a>>y>>b;
		x<<=1; y<<=1;
		x^=a; y^=b;
		add(x^1,y); add(y^1,x);
	}
	for(int i=2; i<=2*n+1; i++) if(!dfn[i]) tarjan(i);
	for(int i=1; i<=n; i++)
	{
		if(c[i*2]==c[(i*2)^1])
		{
			cout<<"IMPOSSIBLE"; return;
		}
	}
	cout<<"POSSIBLE\n";
	for(int i=1; i<=n; i++)
	{
		if(c[i<<1]<c[(i<<1)^1]) cout<<"0 ";else cout<<"1 ";
	}
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);
	
	int T=1;
//	cin>>T;
	while(T--)
	{
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70