2-SAT

前言

其实是一种常用的建图方式。部分内容参考一本通。

算法讲解

简介

2-SAT 问题描述为：给出 $n$ 个布尔变量，每个变量只能取 $0/1$，再给出 $m$ 个约束条件，每个约束条件限制了两个变量的关系，要求找出一组满足所有约束条件的取值方案。
当布尔变量为真时我们称其为原变量，反之为反变量。对于任意一个布尔变量 $x_i$，我们可以用原变量 $i$ 和其反变量 $i’$ 根据约束条件建出有向图，再进行强连通分量并重新建图，进而判断是否有解。

构图

1. $x_i=1$
2. $x_i=0$
3. $x_i\vee x_j=1$（即必有一个为真）
4. $x_i\wedge x_j=0$（即必有一个为假）
5. $x_i XOR x_j=0$
6. $x_i XOR x_j=1$

依次考虑这几种约束条件的构图：

1. 必选 $i$，此种选择方法有多种构图的形式，其中一种就是我们不连边，最后检查 $x_i$ 是否为真，或者说当 $x_i$ 为真时是否存在解。还有一种方法是我们连一条 $i’\rightarrow i$ 的边。其意思为当我们推断出 $x_i$ 为假的时候，$x_i$ 又必须为真。这样连边相当于强制了 $x_i$ 的选择。
2. 必选 $i’$。同理，连 $i\rightarrow i’$ 的边。
3. $i$ 与 $j$ 中至少选择一个，等价于 $xi\vee xj=1$。连边 $i’\rightarrow j$、$j’\rightarrow i$，表示不选 $i$ 就一定要选 $j$，不选 $j$ 就一定要选 $i$。
4. $i$ 与 $j$ 不都选，等价于 $x_i XOR x_j=0$。连边 $i\rightarrow j’$、$j\rightarrow i’$，表示选了 $i$ 就一定不选 $j$，选了 $j$ 就一定不选 $i$。
5. 等价于 $x_iXORx_j=0$。连边 $i\rightarrow j$、$j\rightarrow i$、$i\rightarrow j’$、$j’\rightarrow i’$。
6. 等价于 $x_iXORx_j=1$。连边 $i\rightarrow j’$、$j\rightarrow i’$、$i’\rightarrow j$、$j’\rightarrow i$。

证明与思考

主要是图的对称性和传递性。

对称性

这里的对称指的是逆否命题的对称，即若存在 $i\rightarrow j$ 的边，则一定存在 $j’\rightarrow i’$ 的边，我们称这两条边互为对称边。
不难发现，对称性在建图是已经体现出来。对于 $i\rightarrow i’$ 这样的边，对称边还是自己，仍然满足对称性。

传递性

若有 $i\rightarrow j,j\rightarrow k$，则可得出 $i\rightarrow k$。
由此我们求出来的强连通分量也有对称性。

判定与方案

判定

对于一个变量 $x_i$，我们称 $i$ 与 $i’$ 是矛盾的。
使用 tarjan 算法缩点，如果 $i$ 与 $i’$ 在同一个强连通分量中，则原问题无解，否则无解。

方法

性质：对于建好的图在所选择的集合中任意一个点 $x_i$，点 $x_i$ 的所有后继都应该被选。
那考虑这样构造答案：
我们按照拓扑序从后往前考虑每个强连通分量是否选取，能够避免“选了 $i$ 却发现 $i’$ 在 $i$ 的后继中”的尴尬情况。
其实实现并没有那么麻烦，回顾 tarjan 算法，我们是在回溯的过程中求得强连通分量，所以求强连通分量的顺序就是拓扑逆序。所以我们不用真的求拓扑序。

方案 1

缩点时直接判断当前强连通分量是否能被选取，如果内部没有矛盾且所有点都是可选的，同时设置矛盾点不可选。那么这样选取实际上是遵循了拓扑逆序。

方案 2

按照求强连通分量的顺序给每个强连通分量编号。结束缩点后，对于一堆互相矛盾的点，选择编号较小的那一个（等价于拓扑逆序较小的，即拓扑序从后往前），本质上也遵循了拓扑逆序。

Code(模板)

Code

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
#include<bitset>
#define put putchar
#define ls(k) (k << 1)
#define rs(k) (k << 1 | 1)
#define LL long long

using namespace std;

const int N = 2e6 + 10;

int n, m;
int low[N], dfn[N], cnt = 0;
int q[N], len = 0, scc[N], tot = 0;

int h[N], idx = 0;
struct Edge {
    int to, ne;
} e[N];

template<class T>
 inline void read(T &x) {
    T res = 0, f = 1; char c = getchar();
    while(! isdigit(c)) {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
    x = res * f; return ;
}
template<class T, class ...T1>
inline void read(T &x, T1 &...x1) {
    read(x), read(x1...); return ;
}
template<class T>
inline void write(T x) {
    if(x < 0) x = -x, put('-');
    if(x > 9) write(x / 10);
    put(x % 10 + 48); return ;
}
template<>
inline void write(char x) {
    put(x); return ;
}
template<class T, class ...T1>
inline void write(T x, T1 ...x1) {
    write(x),write(x1...); return ;
}

void add(int a, int b) {
    e[idx] = {b, h[a]}, h[a] = idx ++;
}
void tarjan(int u) {
    dfn[u] = low[u] = ++ cnt; q[++ len] = u;
    for(int i = h[u]; ~i; i = e[i].ne) {
        int v = e[i].to;
        if(! dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        if(! scc[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        scc[u] = ++ tot;
        while(q[len] != u)
            scc[q[len]] = tot, -- len;
        -- len;
    }
}

signed main()
{
   // freopen(".in", "r", stdin);
   // freopen(".out", "w", stdout);
    read(n, m); memset(h, -1, sizeof h);
    for(int i = 1; i <= m; ++ i) {
        int x, vx, y, vy;
        read(x, vx, y, vy);
        add(x + (vx ^ 1) * n, y + vy * n), add(y + (vy ^ 1) * n, x + vx * n);
    }
    for(int i = 1; i <= n * 2; ++ i)
        if(! dfn[i])
            tarjan(i);
    for(int i = 1; i <= n; ++ i)
        if(scc[i] == scc[i + n])
            return puts("IMPOSSIBLE"), 0;
    puts("POSSIBLE");
    for(int i = 1; i <= n; ++ i)
        write(scc[i] < scc[i + n] ? 0 : 1, ' ');
    return 0;
}

例题

P4782 【模板】2-SAT

link，模板。

P4171 [JSOI2010] 满汉全席

link，约等于模板。

Code

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
#include<bitset>
#define put putchar
#define ls(k) (k << 1)
#define rs(k) (k << 1 | 1)
#define LL long long

using namespace std;

const int N = 1e4 + 10;

int n, m, T;
int low[N], dfn[N], cnt;
int q[N], len, scc[N], tot;

int h[N], idx = 0;
struct Edge {
    int to, ne;
} e[N];

template<class T>
 inline void read(T &x) {
    T res = 0, f = 1; char c = getchar();
    while(! isdigit(c)) {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
    x = res * f; return ;
}
template<class T, class ...T1>
inline void read(T &x, T1 &...x1) {
    read(x), read(x1...); return ;
}
template<class T>
inline void write(T x) {
    if(x < 0) x = -x, put('-');
    if(x > 9) write(x / 10);
    put(x % 10 + 48); return ;
}
template<>
inline void write(char x) {
    put(x); return ;
}
template<class T, class ...T1>
inline void write(T x, T1 ...x1) {
    write(x),write(x1...); return ;
}

void add(int a, int b) {
    e[idx] = {b, h[a]}, h[a] = idx ++;
}
void tarjan(int u) {
    dfn[u] = low[u] = ++ cnt; q[++ len] = u;
    for(int i = h[u]; ~i; i = e[i].ne) {
        int v = e[i].to;
        if(! dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        if(! scc[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        scc[u] = ++ tot;
        while(q[len] != u)
            scc[q[len]] = tot, -- len;
        -- len;
    }
}
void get(char& x) {
    x = getchar();
    while(x != 'm' && x != 'h')
        x = getchar();
}

signed main()
{
   // freopen(".in", "r", stdin);
   // freopen(".out", "w", stdout);
    read(T);
    while(T --) {
        read(n, m); 
        memset(h, -1, sizeof h); memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low); memset(scc, 0, sizeof scc);
        idx = cnt = tot = len = 0;
        for(int i = 1; i <= m; ++ i) {
            int x, vx, y, vy; char a, b;
            get(a), read(x), get(b), read(y);
            vx = a == 'm' ? 1 : 0, vy = b == 'm' ? 1 : 0;
            add(x + (vx ^ 1) * n, y + vy * n), add(y + (vy ^ 1) * n, x + vx * n);
        }
        for(int i = 1; i <= n * 2; ++ i)
            if(! dfn[i])
                tarjan(i);
        bool flag = true;
        for(int i = 1; i <= n; ++ i)
            if(scc[i] == scc[i + n]) {
                flag = false; puts("BAD");
                break;
            }
        if(flag)
            puts("GOOD");
    }
    return 0;
}

P5782 [POI2001] 和平委员会

link，也是板。

P3007 [USACO11JAN] The Continental Cowngress G

link，比较有意思，但是数据不够强，支持 $O(n^2)$。
首先正常建边，然后判定也比较好写。主要是是否必要的判断感觉上不太友好。
转化一下：
“?”：通过合法，驳回也合法。
“Y”：只有通过合法。
“N”：只有驳回合法。
那么直接选取这个点，通过判断它的后继中是否有矛盾即可。复杂度 $O(n^2)$。

Code

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
#include<bitset>
#define put putchar
#define ls(k) (k << 1)
#define rs(k) (k << 1 | 1)
#define LL long long

using namespace std;

const int N = 1e4 + 10;

int n, m;
int low[N], dfn[N], cnt;
int q[N], len, scc[N], tot;
bool st[N];

int h[N], idx = 0;
struct Edge {
    int to, ne;
} e[N];

template<class T>
 inline void read(T &x) {
    T res = 0, f = 1; char c = getchar();
    while(! isdigit(c)) {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
    x = res * f; return ;
}
template<class T, class ...T1>
inline void read(T &x, T1 &...x1) {
    read(x), read(x1...); return ;
}
template<class T>
inline void write(T x) {
    if(x < 0) x = -x, put('-');
    if(x > 9) write(x / 10);
    put(x % 10 + 48); return ;
}
template<>
inline void write(char x) {
    put(x); return ;
}
template<class T, class ...T1>
inline void write(T x, T1 ...x1) {
    write(x),write(x1...); return ;
}

void add(int a, int b) {
    e[idx] = {b, h[a]}, h[a] = idx ++;
}
void tarjan(int u) {
    dfn[u] = low[u] = ++ cnt; q[++ len] = u;
    for(int i = h[u]; ~i; i = e[i].ne) {
        int v = e[i].to;
        if(! dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        if(! scc[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        scc[u] = ++ tot;
        while(q[len] != u)
            scc[q[len]] = tot, -- len;
        -- len;
    }
}
void get(char& x) {
    x = getchar();
    while(x != 'Y' && x != 'N')
        x = getchar();
}
void dfs(int u) {
    st[u] = true;
    for(int i = h[u]; ~i; i = e[i].ne)
        if(! st[e[i].to])
            dfs(e[i].to);
    return ;
}
int check(int x) {
    memset(st, 0, sizeof st); dfs(x);
    for(int i = 1; i <= n; ++ i)
        if(st[i] && st[i + n])
            return 0;
    return 1;
}

signed main()
{
   // freopen(".in", "r", stdin);
   // freopen(".out", "w", stdout);
    read(n, m); memset(h, -1, sizeof h);
    for(int i = 1; i <= m; ++ i) {
        int x, vx, y, vy; char a, b;
        read(x), get(a), read(y), get(b);
        vx = a == 'Y' ? 1 : 0, vy = b == 'Y' ? 1 : 0;
        add(x + (vx ^ 1) * n, y + vy * n), add(y + (vy ^ 1) * n, x + vx * n);
    }
    for(int i = 1; i <= n * 2; ++ i)
        if(! dfn[i])
            tarjan(i);
    for(int i = 1; i <= n; ++ i)
        if(scc[i] == scc[i + n])
            return puts("IMPOSSIBLE"), 0;
    for(int i = 1; i <= n; ++ i) {
        int vx = check(i), vy = check(i + n);
        if(vx && vy)
            write('?');
        else if(vx)
            write('N');
        else
            write('Y');
    }
    return 0;
}

P3209 [HNOI2010] 平面图判定

link，需要一点前置芝士。
首先跟据欧拉公式（$|V|+|R|-|E|=2$）和平面图定理（$m\leq n\times 3+6$），先将边数缩减到 $O(n)$ 级别。
然后把点的编号转化为哈密顿回路中的顺序编号，同时判断哪两条边相交（对于边 $i,j$ 判断相交：$x_i<x_j<y_i<y_j$）。
由于边可以放在哈密顿回路内部，也可以放在外部，那么既可以用种类并查集做，也可以用 $2-SAT$ 做，最后判断是否存在合法解即可。

Code(并查集)

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
#include<bitset>
#define put putchar
#define ls(k) (k << 1)
#define rs(k) (k << 1 | 1)
#define LL long long

using namespace std;

const int N = 1e4 + 10;

int n, m, T;
int id[N], a[N];
int f[N];

struct Edge {
    int u, v;
} e[N];

template<class T>
 inline void read(T &x) {
    T res = 0, f = 1; char c = getchar();
    while(! isdigit(c)) {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
    x = res * f; return ;
}
template<class T, class ...T1>
inline void read(T &x, T1 &...x1) {
    read(x), read(x1...); return ;
}
template<class T>
inline void write(T x) {
    if(x < 0) x = -x, put('-');
    if(x > 9) write(x / 10);
    put(x % 10 + 48); return ;
}
template<>
inline void write(char x) {
    put(x); return ;
}
template<class T, class ...T1>
inline void write(T x, T1 ...x1) {
    write(x),write(x1...); return ;
}

bool check(Edge a, Edge b) {
    if(id[a.u] < id[b.u] && id[b.u] < id[a.v] && id[a.v] < id[b.v])
        return true;
    if(id[b.u] < id[a.u] && id[a.u] < id[b.v] && id[b.v] < id[a.v])
        return true;
    return false;
}
int Find(int x) {
    return f[x] == x ? x : Find(f[x]);
}
void get_ans() {
    if(m > n * 3 + 6)
        return (void)(puts("NO"));
    for(int i = 1; i <= n * 2; ++ i)
        f[i] = i;
    for(int i = 1; i <= m; ++ i)
        if(id[e[i].u] > id[e[i].v])
            swap(e[i].u, e[i].v);
    for(int i = 1; i <= m; ++ i)
        for(int j = i + 1; j <= m; ++ j) {
            if(check(e[i], e[j])) {
                int fi = Find(i), fj = Find(j);
                if(fi == fj)
                    return (void)(puts("NO"));
                f[fi] = Find(j + n), f[fj] = Find(i + n);
            }
        }
    puts("YES");
    return ;
}
signed main()
{
   // freopen(".in", "r", stdin);
   // freopen(".out", "w", stdout);
    read(T);
    while(T --) {
        read(n, m);
        for(int i = 1; i <= m; ++ i)
            read(e[i].u, e[i].v);
        for(int i = 1; i <= n; ++ i)
            read(a[i]), id[a[i]] = i;
        get_ans();
    }
    return 0;
}

Code(2-SAT)

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const int V = 205, N = 3e4 + 5, M = 2e6 + 5;
int n, m, eX[N], eY[N], Cir[V], ecnt, nxt[M], adj[N], go[M], dfn[N], low[N],
top, times, stk[N], bel[N], sum, rev[V], Ex[N], Ey[N];
bool cir[V][V], ins[N];
void add_edge(int u, int v) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
}
void Tarjan(int u) {
    dfn[u] = low[u] = ++times;
    stk[++top] = u; ins[u] = 1;
    for (int e = adj[u], v; e; e = nxt[e])
        if (!dfn[v = go[e]]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    if (dfn[u] == low[u]) {
        int v; bel[u] = ++sum; ins[u] = 0;
        while (v = stk[top--], v != u) bel[v] = sum, ins[v] = 0;
    }
}
bool check() {
    int i; for (i = 1; i <= (m << 1); i++)
        if (!dfn[i]) Tarjan(i);
    for (i = 1; i <= m; i++)
        if (bel[i] == bel[i + m]) return 0;
    return 1;
}
void work() {
    ecnt = times = sum = 0; memset(adj, 0, sizeof(adj));
    memset(dfn, 0, sizeof(dfn)); memset(bel, 0, sizeof(bel));
    memset(low, 0, sizeof(low)); memset(cir, 0, sizeof(cir));
    int i, j, u, v, x, y, tot = 0; n = read(); m = read();
    for (i = 1; i <= m; i++) {
        eX[i] = read(); eY[i] = read();
        if (eX[i] > eY[i]) swap(eX[i], eY[i]);
    }
    for (i = 1; i <= n; i++) {
        rev[Cir[i] = read()] = i;
        if (i > 1) {
            x = Cir[i - 1]; y = Cir[i];
            if (x < y) cir[x][y] = 1;
            else cir[y][x] = 1;
        }
    }
    if (m > 3 * n - 6) return (void) (printf("NO\n"));
    x = Cir[n]; y = Cir[1]; ((x < y) ? cir[x][y] : cir[y][x]) = 1;
    for (i = 1; i <= m; i++) {
        if (cir[eX[i]][eY[i]]) continue;
        Ex[++tot] = eX[i]; Ey[tot] = eY[i];
    }
    m = tot; for (i = 1; i < m; i++) for (j = i + 1; j <= m; j++) {
        u = rev[Ex[i]], v = rev[Ey[i]], x = rev[Ex[j]], y = rev[Ey[j]];
        if (u > v) swap(u, v); if (x > y) swap(x, y);
        if ((u < x && v > x && v < y) || (u > x && u < y && v > y)) {
            add_edge(i, j + m); add_edge(i + m, j);
            add_edge(j, i + m); add_edge(j + m, i);
        }
    }
    printf(check() ? "YES\n" : "NO\n");
}
int main() {
    int T = read();
    while (T--) work();
    return 0;
}