2-SAT问题学习笔记

### 1. 简单理解

在2-SAT问题中，我们需要处理一系列事件，每个事件有两个可能的结果A或B。同时，给定一些约束条件，即某些组合不能同时发生。目标是找到一个满足所有约束条件的解决方案。

### 2. 模型构建

假设我们有若干个事件，每个事件有两种结果A和B。如果某个事件的结果为A，则另一事件的结果不能为B。为了表示这种关系，我们可以用有向图来建模：
- 如果事件1的结果为A，则事件2的结果必须为A。这可以通过一条从(1, A)到(2, A)的有向边来表示。
- 类似地，如果事件1的结果为A，则事件2的结果不能为B，可以表示为从(1, A)到(2, B')的有向边，其中B'表示B的对立面。

### 3. 算法概述

由于构建的是有向图，可以使用强连通分量（SCC）算法来解决问题。具体步骤如下：
1. 构建有向图，根据约束条件添加有向边。
2. 使用Tarjan算法或Kosaraju算法求解强连通分量。
3. 如果某个事件的两种结果出现在同一个强连通分量中，则问题无解。
4. 否则，可以通过拓扑排序或其他方法确定每个事件的结果。

### 4. 实例分析

#### 和平委员会问题

**问题描述**：
某国有n个党派，每个党派在议会中有两个代表。现在要成立和平委员会，需满足以下条件：
1. 每个党派在和平委员会中恰好有一个代表。
2. 如果两个代表不和，则他们不能同时属于委员会。

**输入格式**：
第一行包含两个整数n和m，分别表示党派数量和m对不和的关系。接下来m行每行两个整数a, b，表示编号为a和b的代表不和。

**输出格式**：
如果能成立，则输出构成委员会的代表的编号，且字典序最小。如果不能成立，则输出'NIE'。

**数据范围**：
1 ≤ n ≤ 8000，0 ≤ m ≤ 20000。

**代码实现**：
```cpp
#include
#include
using namespace std;
const int maxn = 8005;
const int maxm = 20005;
int n, m, np = 0, last[maxn * 2], op[maxn * 2];
struct edge { int to, pre; } E[maxm * 2];

char c;
void qkscanf(int &x) {
for (c = getchar(); c <'0' || c > '9'; c = getchar());
for (x = 0; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
}

char num[10]; int ct;
void qkprintf(int x) {
ct = 0;
if (!x) num[ct++] = '0';
while (x) num[ct++] = x % 10 + '0', x /= 10;
while (ct--) putchar(num[ct]);
putchar('\n');
}

void addedge(int u, int v) {
E[++np] = (edge){v, last[u]};
last[u] = np;
}

int vis[maxn * 2], stk[maxn * 2], top = 0;
bool DFS(int i) {
if (vis[op[i]]) return 0;
if (vis[i]) return 1;
stk[++top] = i;
vis[i] = 1;
for (int p = last[i]; p; p = E[p].pre) {
int j = E[p].to;
if (!DFS(j)) return 0;
}
return 1;
}

int main() {
qkscanf(n); qkscanf(m);
for (int i = 1; i <= n * 2; i++) op[i] = i % 2 ? i + 1 : i - 1;
int x, y;
for (int i = 1; i <= m; i++) {
qkscanf(x); qkscanf(y);
addedge(x, op[y]);
addedge(y, op[x]);
}
for (int i = 1; i <= n * 2; i++) {
if (vis[i] || vis[op[i]]) continue;
top = 0;
if (!DFS(i)) {
while (top) vis[stk[top--]] = 0;
if (!DFS(op[i])) {
puts("NIE");
return 0;
}
}
}
for (int i = 1; i <= n * 2; i++) if (vis[i]) qkprintf(i);
return 0;
}
```

### 5. 学习建议

1. **多做练习题**：建议先从简单的模板题入手，逐步理解2-SAT的核心思想和常见技巧。
2. **理解对立面**：明确什么情况下需要连接对立面，这是解决2-SAT问题的关键。
3. **掌握算法**：Tarjan算法是求解强连通分量的经典方法，值得深入学习。
4. **优化细节**：如使用DFS+栈代替Tarjan算法，可以在实际应用中获得更好的性能。