由
由
对
对
称
称
性
性
解
解
2-SAT
2-SAT
问
问
题
题
2-SAT:
2-SAT:
2-SAT就是2判定性问题，是一种特殊的逻辑判
定问题。
2-SAT问题有何特殊性？该如何求解？
我们从一道例题来认识2-SAT问题，并提出对
一类2-SAT问题通用的解法。
Poi 0106 Peaceful Commission
Poi 0106 Peaceful Commission
[
[
和
和
平
平
委
委
员
员
会
会
]
]
某国有n个党派，每个党派在议会中恰有2个代表。
现在要成立和平委员会 ，该会满足：
每个党派在和平委员会中有且只有一个代表
如果某两个代表不和，则他们不能都属于委员会
代表的编号从1到2n，编号为2a-1、2a的代表属于第a
个党派
输入n（党派数），m（
不友好对数）及m对两
两不和的代表编号
其中1≤n≤8000，0≤m
≤20000
求和平委员会是否能
创立。
若能，求一种构成方
式。
例：输入：3 2 输出：1
1 3 4
2 4 5
分
分
析
析
：
：
原题可描述为：
有n个组，第i个组里有两个节点A
i
, A
i
' 。需要从每个
组中选出一个。而某些点不可以同时选出（称之为
不相容）。任务是保证选出的n个点都能两两相容
。
（在这里把A
i
, A
i
' 的定义稍稍放宽一些，它们同
时表示属于同一个组的两个节点。也就是说，如
果我们描述A
i
，那么描述这个组的另一个节点就
可以用A
i
'）
