跳转至

2-SAT

\(a\vee b\)

建边 \(!a->b\) 和 \(!b->a\)。

当一个点的两个状态属于一个强连通分量时，无解。

选择强联通分量序号小的方案。

例题

P4782 【模板】2-SAT 问题 - 洛谷

C++
 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
int main() {
    int n, m;
    cin >> n >> m;
    Graph g(2 * n + 1);
    for (int i = 1 ; i <= m ; i++) {
        int x, a, y, b;
        cin >> x >> a >> y >> b;
        x *= 2; y *= 2;
        g.addEdge(x + !a, y + b);
        g.addEdge(y + !b, x + a);
    }
    g.scc();
    auto bel = g.bel;
    for (int i = 2 ; i <= 2 * n + 1 ; i += 2) {
        if (bel[i] == bel[i + 1]) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    cout << "POSSIBLE\n";
    for (int i = 2 ; i <= 2 * n + 1 ; i += 2) {
        if (bel[i] > bel[i + 1]) {
            cout << 1 << " ";
        } else {
            cout << 0 << " ";
        }
    }
    return 0;
}
习题

P5782 [POI2001] 和平委员会 - 洛谷

如果 \(x\) 和 \(y\) 有冲突，那么 \(x\) 只能和 \(y\) 的伙伴一起，或 \(x\) 的伙伴和 \(y\) 一起。

\(2i-1\) 和 \(2i\) 必须不在同一强连通分量

C++
 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
int main() {
    int n, m;
    cin >> n >> m;
    Graph g(2 * n + 1);
    for (int i = 1 ; i <= m ; i++) {
        int x, y;
        cin >> x >> y;
        g.addEdge(x, y + (y % 2 == 0 ? -1 : 1));
        g.addEdge(y, x + (x % 2 == 0 ? -1 : 1));
    }
    g.scc();
    auto bel = g.bel;
    for (int i = 1 ; i <= 2 * n ; i += 2) {
        if (bel[i] == bel[i + 1]) {
            cout << "NIE\n";
            return 0;
        }
    }
    for (int i = 1 ; i <= 2 * n ; i += 2) {
        if (bel[i] < bel[i + 1]) {
            cout << i << "\n";
        } else {
            cout << i + 1 << "\n";
        }
    }
    return 0;
}