2-SAT 问题

解题思路

本题是 2-SAT 问题的模板题，对于每个条件 $a \wedge b$，得出推导公式 $-a \rightarrow b$ 和 $-b \rightarrow a$，按照推导公式建图，然后求强连通分量并进行缩点，如果任意一个变量的两种取值在同一个强连通分量中，说明无解。否则枚举每个变量，选取所在强连通分量拓扑序靠后的取值。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2000010;

int n, m;
int h[N], e[N], ne[N], idx; //邻接表
int dfn[N], low[N], timestamp; //Tarjan 算法的数组
int stk[N], top; //栈
bool in_stk[N]; //记录每个点是否在栈中
int id[N], cnt; //记录每个点所在的强连通分量编号

void add(int a, int b) //添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) //求强连通分量
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if(low[u] == dfn[u])
    {
        int y;
        cnt++;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = cnt;
        } while(y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h); //初始化邻接表

    //对于 x[i]，设 2 * i 表示 x[i] 取 0，2 * i + 1 表示 x[i] 取 1
    while(m--)
    {
        int i, a, j, b;
        scanf("%d%d%d%d", &i, &a, &j, &b);
        i--, j--; //编号从 0 开始
        add(2 * i + !a, 2 * j + b); //-a -> b
        add(2 * j + !b, 2 * i + a); //-b -> a
    }

    //求强连通分量
    for(int i = 0; i < 2 * n; i++)
        if(!dfn[i])
            tarjan(i);

    //判断是否有解
    for(int i = 0; i < n; i++)
        if(id[i * 2] == id[i * 2 + 1]) //如果某一个变量的两个取值在同一个强连通分量中，说明无解
        {
            puts("IMPOSSIBLE");
            return 0;
        }

    puts("POSSIBLE");
    for(int i = 0; i < n; i++)
        if(id[i * 2] < id[i * 2 + 1]) printf("0 "); //优先取拓扑序靠后的取值，即所在强连通分量靠前的取值
        else printf("1 ");

    return 0;
}