题解：2-SAT问题

一、题目分析

本题给定(n)个未赋值的布尔变量(x_1\sim x_n)和(m)个条件，每个条件形式为“(x_i)为(0/1)或(x_j)为(0/1)至少有一项成立”，要求对这(n)个布尔变量进行赋值（(0)或(1)），使得所有(m)个条件都能成立。若有解，输出赋值结果；若无解，输出“IMPOSSIBLE” 。

二、解题思路

本题通过将2-SAT问题转化为图论中的强连通分量问题，利用Tarjan算法求解。

（一）变量与条件的图论建模

将每个布尔变量(x_i)拆分成两个节点：(2i)表示(x_i)为(0)，(2i + 1)表示(x_i)为(1) 。对于每个条件“(x_i)为(a)或(x_j)为(b)”（(a,b\in{0,1})），可以转化为逻辑关系，然后在图中添加两条有向边：
- 若(x_i)为(a)不成立，则(x_j)必须为(b)，即从节点(2i + !a)指向节点(2j + b)。
- 若(x_j)为(b)不成立，则(x_i)必须为(a)，即从节点(2j + !b)指向节点(2i + a)。

（二）Tarjan算法求强连通分量

Tarjan算法用于在有向图中寻找强连通分量。强连通分量是指图中任意两个节点之间都存在路径的子图。具体步骤如下：
1. 初始化：定义时间戳(ts)用于记录节点的访问顺序，栈(stk)用于存储正在访问的节点，数组(dfn)记录每个节点的首次访问时间，(low)记录每个节点及其子树能追溯到的最早的首次访问时间。
2. 深度优先搜索：从每个未访问的节点(u)开始进行深度优先搜索。
- 当访问到节点(u)时，初始化(dfn[u] = low[u] = ++ts)，将(u)入栈并标记为在栈中。
- 遍历节点(u)的所有出边，对于每条边指向的节点(j)：
- 若(j)未被访问过，递归调用(tarjan(j))，并更新(low[u] = min(low[u], low[j]))。
- 若(j)在栈中，说明存在环，更新(low[u] = min(low[u], dfn[j]))。
3. 确定强连通分量：当(low[u] = dfn[u])时，说明找到了一个强连通分量。不断从栈中弹出节点，直到弹出节点(u)，并给这些节点标记相同的强连通分量编号。

（三）判断是否有解及赋值

1. 判断是否有解：对于每个布尔变量(x_i)，若表示(x_i)为(0)的节点(2i)和表示(x_i)为(1)的节点(2i + 1)在同一个强连通分量中，即(id[2i] = id[2i + 1])，则说明无解。因为这意味着(x_i)为(0)和(x_i)为(1)这两种情况必须同时成立，这与布尔变量的定义矛盾。
2. 赋值：若有解，对于每个布尔变量(x_i)，比较其表示为(0)和(1)的节点所在强连通分量的编号。若(id[2i] < id[2i + 1])，则令(x_i = 0)；否则令(x_i = 1) 。

三、代码实现细节

（一）头文件与全局变量

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 2000010, M = 2000010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts, stk[N], top;
int id[N], cnt;
bool ins[N];

• 引入输入输出、字符串操作、算法相关头文件以及标准输入输出头文件。
• 定义常量(N)和(M)分别表示节点数和边数的上限。
• 定义变量(n)和(m)分别表示布尔变量的个数和条件的个数。
• 定义邻接表相关数组(h)、(e)、(ne)和(idx)用于存储图的边信息。
• 定义(dfn)和(low)数组用于Tarjan算法，(ts)表示时间戳，(stk)和(top)用于实现栈，(id)数组记录每个节点所属的强连通分量编号，(cnt)表示强连通分量的个数，(ins)数组用于标记节点是否在栈中。

（二）添加边函数add

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

该函数用于向邻接表中添加一条从节点(a)到节点(b)的有向边。

（三）Tarjan算法函数tarjan

void tarjan(int u)
{
    dfn[u] = low[u] = ++ ts;
    stk[ ++ top] = u, ins[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (ins[j]) low[u] = min(low[u], dfn[j]);
    }

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

• 函数开始时，初始化(dfn[u])和(low[u])，将(u)入栈并标记在栈中。
• 遍历(u)的所有出边，根据边指向节点(j)的访问情况更新(low[u])。
• 当(low[u] = dfn[u])时，从栈中弹出节点并标记它们属于同一个强连通分量。

（四）main函数

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    while (m -- )
    {
        int i, a, j, b;
        scanf("%d%d%d%d", &i, &a, &j, &b);
        i --, j -- ;
        add(2 * i + !a, 2 * j + b);
        add(2 * j + !b, 2 * i + a);
    }

    for (int i = 0; i < n * 2; 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;
}

• 读取(n)和(m)，初始化邻接表。
• 遍历每个条件，根据条件在图中添加相应的有向边。
• 对每个未访问的节点调用(tarjan)算法，求出所有强连通分量。
• 检查每个布尔变量对应的两个节点是否在同一个强连通分量中，判断是否有解。
• 若有解，根据节点所在强连通分量的编号对布尔变量进行赋值并输出。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 建图阶段：遍历(m)个条件，每个条件添加两条边，时间复杂度为(O(m))。
• Tarjan算法阶段：对图中的每个节点和边进行一次访问，图中节点数为(2n)，边数最多为(2m)，时间复杂度为(O(2n + 2m)=O(n + m))。
• 因此，总的时间复杂度为(O(n + m))。

（二）空间复杂度

• 邻接表存储图的边信息，最多有(2m)条边，空间复杂度为(O(m))。
• 其他辅助数组如(dfn)、(low)、(id)等，大小为(2n)，空间复杂度为(O(n))。
• 所以，总的空间复杂度为(O(n + m))。