2-SAT问题

2-SAT问题

九月 05, 2021

2-SAT问题

描述

有n个组，第i个组里有两个节点$A_i, A_i’$ 。需要从每个组中选出一个。而某些点不可以同时选出（称之为不相容）。任务是保证选出的n个点都能两两相容。这类型的问题我们称之为2-SAT问题

问题引入

Question

某国有N个党派，每个党派里面有且只有两个代表（编号连续），要求从中选一个代表出来组成和平委员会，且如果两个代表不和，则他们不能同时属于委员会

Sample Input

1
2
3
3 2
1 3
2 4

Sample Output

1
2
3
1 
4
5

Analysis

理解

可以通过图论知识来解决，如果选1,则不能选4,只能选3,而如果选4，则只能选2，所以我们根据这个来建立有向边。

$Conclusion$:若所有$i_1,i_2$都不在同一个强分支，则有解。

对于判定强分支有以下的方法

  • $Kusarajo$,$Tarjan$
  • 染色法

这里选择使用染色法

染色法

从每一个组别开始去$dfs$,将要选择的点依次标记出来，并把其相关的必选点也同样染色，如果出现了冲突，则清除染色方案，重新染色。

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
//color是标记颜色的，other记录同一组中另外一个元素是多少
//stk是手动的栈，这里采用链式前向星存图
bool DFS(int u){
	if(color[u])return true;
	if(color[other[u]])return false;
	color[u]=true;
	stk[++top]=u;//记录 
	for(int i=head[u];i;i=nxt[i])
		if(!DFS(to[i]))return false;
	return true;
}

bool twoSAT(){
	memset(color,false,sizeof(color));
	for(int i=1;i<=N;i++){
		if(color[2*i-1]||color[2*i])continue;
		//已经染过了色 
		top=0;
		if(!DFS(2*i-1)){
			while(top)color[stk[top]]=false,top--;
			if(!DFS(2*i))return false;
		}
	}
	return true;
}

这里来说一下这一段代码

1
2
3
for(int i=head[u];i;i=nxt[i])
		if(!DFS(to[i]))return false;
	return true;

注意这里不可以写成

1
return DFS(to[i]);

因为这一点染色是否成功要看与之相关的所有的点的染色是否成功，而如果有相关一个点失败了，那么就是失败了，要回去重新$dfs$

Codes

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
#include<bits/stdc++.h>
#define maxn 8005
#define maxm 20005
using namespace std;

int other[maxn*2],ans[maxn],N,M,tot=0;
int head[maxn],to[maxm],nxt[maxm];
bool color[maxn];int stk[maxn],top=0;

inline int read(){
	int res=0;int sign=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')sign=-1;c=getchar();}
	while(c<='9'&&c>='0'){res=res*10+c-48;c=getchar();}
	return res*sign;
} 
void init(int K){
	for(int i=1;i<=2*K;i++)
		other[i]=(i&1)?i+1:i-1;
}
inline void addedge(int x,int y){
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
bool DFS(int u);
bool twoSAT();

int main(){
	N=read();M=read();
	init(N);
	for(int i=1;i<=M;i++){
		int a=read(),b=read();
		addedge(a,other[b]);
		addedge(b,other[a]);
		//a,b之间是相互冲突的，如果a选了的话，那么就
		//必须要选b所在组别的另外一个，如果是b选了同理 
	} 
	if(twoSAT()){
		for(int i=1;i<=2*N;i++)if(color[i])printf("%d\n",i);
	}
	else printf("NIE");
	return 0;
}

bool DFS(int u){
	if(color[u])return true;
	if(color[other[u]])return false;
	color[u]=true;
	stk[++top]=u;//记录 
	for(int i=head[u];i;i=nxt[i])
		if(!DFS(to[i]))return false;
	return true;
}

bool twoSAT(){
	memset(color,false,sizeof(color));
	for(int i=1;i<=N;i++){
		if(color[2<<i-1]||color[2*i])continue;
		//已经染过了色 
		top=0;
		if(!DFS(2*i-1)){
			while(top)color[stk[top]]=false,top--;
			if(!DFS(2*i))return false;
		}
	}
	return true;
}

例题

洛谷P4782

链接：洛谷P4782

Analysis

就和它自己说的一样，这是一道模板题，这里选择把真和假的两种状态作为所说的选择。所以就选择用$i$表示这一个点要选，$i+N$来表示这一个点不选

Codes

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
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;

int color[maxn<<1],N,M,other[maxn<<1];
int stk[maxn<<1],top=0;
int head[maxn<<1],to[maxn<<1],nxt[maxn<<1],tot=0;
//i表示 这一个节点真,i+N表示假 
inline int read(){
	int res=0,sign=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')sign=-1;c=getchar();}
	while(c<='9'&&c>='0'){res=res*10+c-48;c=getchar();}
	return res*sign;
}

void init(int K){
	for(int i=1;i<=2*K;i++)
		other[i]=(i<=K)?(i+K):(i-K);
}

inline void add(int x,int y){
	to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}

bool DFS(int u);
bool twoSAT();

int main(){
	N=read();M=read();
	init(N);
	int a,b,c,d;
	for(int i=1;i<=M;i++){
		a=read();b=read();
		c=read();d=read();
		add(a+!b*N,c+d*N);
		add(c+!d*N,a+b*N);
	}
	if(twoSAT()){
		printf("POSSIBLE\n");
		for(int i=1;i<=N;i++){
			printf("%d ",color[i]<color[i+N]);
		}
	}
	else printf("IMPOSSIBLE");
	return 0;
}

bool DFS(int u){
	if(color[u])return true;
	if(color[other[u]])return false;
	color[u]=true;
	stk[++top]=u;
	for(int i=head[u];i;i=nxt[i])
		if(!DFS(to[i]))return false;
	return true;
}

bool twoSAT(){
	memset(color,0,sizeof(color));
	for(int i=1;i<=N;i++){
		if(color[i]||color[i+N])continue;
		top=0;
		if(!DFS(i)){
			while(top)color[stk[top]]=false,top--;
			if(!DFS(i+N))return false;
		}
	}
	return true;
}

洛谷P4171

链接：洛谷P4171

Analysis

这题里面一种材料要么就只能做满洲菜，要么就做汉族菜，因此每一种材料，汉族菜和满洲菜就相当于是对应着$true$和$false$两种状态了，因此就这样来染色法解决问题。这一道题最需要注意的是在于输入时，每一道菜的序号不一定只有一位数。

Codes

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
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
#define maxn 105
#define maxm 1005
using namespace std;
int head[maxn<<1],to[maxm<<1],nxt[maxm<<1],tot=0;
int stk[maxn<<1],top=0;
int col[maxn<<1],other[maxn<<1],N,M,K;

inline int read(){
	int res=0,sign=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')sign=-1;c=getchar();}
	while(c<='9'&&c>='0'){res=res*10+c-48;c=getchar();}
	return res*sign;
}

void init(int K){
	for(int i=1;i<=K;i++)
		other[i]=i+N,other[i+N]=i;;
}

inline void add(int x,int y){
	to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}

bool dfs(int u);
bool twoSAT();

int main(){
	K=read();
	while(K--){
		N=read();M=read();
		init(N);
		for(int i=1;i<=M;i++){
			int x=0,y=0,rep=1;
			char kd[5];
			cin>>kd;
			while(kd[rep]>='0'&&kd[rep]<='9'){
				x=x*10+kd[rep]-48;
				rep++;
			} 
			if(kd[0]=='m')x+=N;
			cin>>kd;
			rep=1;
		 	while(kd[rep]>='0'&&kd[rep]<='9'){
				y=y*10+kd[rep]-48;
				rep++;
			}  
			if(kd[0]=='m')y+=N;//注意这里的输入很重要
			add(x,other[y]);
			add(y,other[x]);
		}
		if(twoSAT())printf("GOOD\n");
		else printf("BAD\n");
		memset(other,0,sizeof(other));
		memset(to,0,sizeof(to));
		memset(head,0,sizeof(head));
		memset(nxt,0,sizeof(nxt));
		tot=0;
	}
}

bool dfs(int u){
	if(col[u])return true;
	if(col[other[u]])return false;
	col[u]=1;
	stk[++top]=u;
	for(int i=head[u];i;i=nxt[i])
		if(!dfs(to[i]))return false;
	return true;
}

bool twoSAT(){
	memset(col,0,sizeof(col));
	for(int i=1;i<=N;i++){
		if(col[i]||col[i+N])continue;
		top=0;
		if(!dfs(i)){
			while(top)col[stk[top]]=0,top--;
			if(!dfs(i+N))return false;
		}
	}
	return true;
}
  1. 1. 2-SAT问题
    1. 1.1. 描述
    2. 1.2. 问题引入
      1. 1.2.1. Question
      2. 1.2.2. Sample Input
      3. 1.2.3. Sample Output
      4. 1.2.4. Analysis
        1. 1.2.4.1. 理解
        2. 1.2.4.2. 染色法
      5. 1.2.5. Codes
    3. 1.3. 例题
      1. 1.3.1. 洛谷P4782
        1. 1.3.1.1. Analysis
        2. 1.3.1.2. Codes
      2. 1.3.2. 洛谷P4171
        1. 1.3.2.1. Analysis
        2. 1.3.2.2. Codes