题解：P4782 【模板】2-SAT

chu_yh · 2025-07-28 16:27:43 · 题解

尝试用了新版格式。我发现氧洛谷在新版格式有不小 bug，在此催更。

定义

2-SAT，简单的说就是给出 n 个布尔方程，每个方程和两个变量相关，如 a \vee b，表示变量 a, b 至少满足一个。然后判断是否存在可行方案，显然可能有多种选择方案，一般题中只需要求出一种即可。另外，\neg a 表示 a 取反。

例题引入：洛谷 P4782

有 n 个布尔变量 x_1\sim x_n，另有 m 个需要满足的条件，每个条件的形式都是“x_i 为 true / false 或 x_j 为 true / false”。比如“x_1 为真或 x_3 为假”、“x_7 为假或 x_2 为假”。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

转化题意为：装饰一个房间，有 m 种装饰品。有 n 个人，每人提出两点要求（要不要用某种装饰品），当其中至少有一条被满足时（当然允许两条都满足），这个人会感到满意。问你是否可以让所有人都感到满意，进一步的，还可以让你输出让所有人都感到满意的方案。

重点：建图

使用布尔方程表示上述问题。设 a 表示要用第 A 种装饰品（\neg a 就表示不用第 A 种装饰品）。如果有个人提出的要求分别是 a 和 b，即 (a \vee b)（变量 a, b 至少满足一个）。对这些变量关系建有向图，则把 a 成立或不成立用图中的点表示，\neg a\to b \neg b\to a，表示 a 不成立则 b 一定成立；同理，b 不成立则 a 一定成立。建图之后，我们就可以使用缩点算法来求解 2-SAT 问题了。

许多 2-SAT 问题都需要找出如 a 不成立，则 b 成立的关系。

求解

思考如果两点在同一强连通分量里有什么含义。根据前文边的逻辑意义可知：若两点在同一强连通分量内，则这两点代表的条件要么都满足，要么都不满足。

建图周我们跑一遍 Tarjan 找 SCC，判断对于任意布尔变量 a， 表示 a 成立的点和表示 a 不成立的点是否在同一个 SCC 中（同一条件不可能既满足又不满足，或既不满足，又并非不满足），若有则输出无解，否则有解。

输出方案时可以通过变量在图中的拓扑序确定该变量的取值。如果变量 x 的拓扑序在 \neg x 之后，那么取 x 值为真。应用到 Tarjan 算法的缩点，即 x 所在 SCC 编号在 \neg x 之前时，取 x 为真。因为 Tarjan 算法求强连通分量时使用了栈，如果跑完 Tarjan 缩点之后呈现出的拓扑序更大，在 Tarjan 会更晚被遍历到，就会更早地被弹出栈而缩点，分量编号会更小，所以 Tarjan 求得的 SCC 编号相当于反拓扑序。

算法会把整张图遍历一遍，并且在结算答案时复杂度为 O(n)，认为 n 和 m 同阶，复杂度为 O(n)。

::::info[代码]

#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
const int N=2e6+2;
int n,m,dfn[N],low[N],t,tot,head[N],a[N];
bool vis[N];
stack<int> s;
struct node{int to,Next;}e[N];

void adde(int u,int v){
    e[++tot].to=v;
    e[tot].Next=head[u];
    head[u]=tot;
}

void Tarjan(int u){
    dfn[u]=low[u]=++t;
    s.push(u);
    vis[u]=1;
    for(int i=head[u];i;i=e[i].Next){
        int v=e[i].to;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        int cur;
        ++tot;
        do{
            cur=s.top();
            s.pop();
            vis[cur]=0;
            a[cur]=tot;
        }while(cur!=u);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,I,J,A,B;i<=m;i++){
        scanf("%d%d%d%d",&I,&A,&J,&B);
        adde(A?I+n:I,B?J:J+n);
        adde(B?J+n:J,A?I:I+n);
    }
    tot=0;
    for(int i=1;i<=(n<<1);i++) if(!dfn[i]) Tarjan(i);
    for(int i=1;i<=n;i++){
        if(a[i]==a[i+n]){
            printf("IMPOSSIBLE");
            return 0;
        }
    }
    puts("POSSIBLE");
    for(int i=1;i<=n;i++){
        putchar(a[i]<a[i+n]?'1':'0');
        putchar(' ');
    }
    return 0;
}

::::