2-SAT问题

众所周知，2-SAT即二元适配性问题，用于解决一类布尔方程的求值问题……

有 $n$ 个布尔变量 $x_1, x_2, …,x_n$，给定 $m$ 对冲突关系，形如 $x_i\And x_j=0$，问一组可行解。
$n\le 10^5, m\le 10^6$

拆点建图，对每个变量 $x_i$ 拆成两个点 $i$ 和 $i’$，前者表示“$x_i$ 为真”，后者表示“$x_i$ 为假”。则可以将冲突关系 $(x_i,x_j)$ 转化为偏序关系 $(i,j’)$ 和 $(j,i’)$，依此得到一张有向图，然后就可以按照处理偏序关系的思路去做了。

容易发现，对于一个偏序环上的点，如果取一个值为真，那么剩下的点取值也必然为真；于是可以得到解的存在性定理：该布尔方程有解当且仅当 $\forall i$，$i$ 和 $i’$ 不在同一个偏序环上。

如何求出一组可行解呢？贪心地想，对于 $i$ 和 $i’$，我们应该选择在新图中拓扑序大的那个将其设为真，因为这样可以最小化影响。注意到 tarjan 求出的 SCC 的编号即为新图拓扑序的反序，因此直接判断即可。

一道栗题

有 $n$ 个布尔变量 $x_1\sim x_n$，另有 $m$ 个需要满足的条件，每个条件的形式都是 「$x_i$ 为 true / false 或 $x_j$ 为 true / false」。比如 「$x_1$ 为真或 $x_3$ 为假」、「$x_7$ 为假或 $x_2$ 为假」。
试给每个变量赋值使得所有条件得到满足，无解输出 IMPOSSIBLE。
$n, m\le 10^6$

容易发现一共有三种本质不同的条件形式：

1. $x_i=0|x_j=1$，等价于 $x_i\And \neg x_j=0$，连边 $(i,j),(j’,i’)$；
2. $x_i=0|x_j=0$，等价于 $x_i\And x_j=0$，连边 $(i,j’),(j,i’)$；
3. $x_i=1|x_j=1$，等价于 $\neg x_i\And \neg x_j=0$，连边 $(i’,j),(j’,i)$。

然后套用上面的做法就好了，代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

const int CN = 4e6 + 6;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]),hd[x] = ecnt;}

int n, m, du[CN];

int dfn[CN], low[CN], idx = 0, stk[CN], top = 0, bel[CN], bcnt = 0; bool ins[CN];
void dfs(int u){
    dfn[u] = low[u] = ++idx, stk[++top] = u, ins[u] = true;
    for(int k = hd[u]; k; k = E[k].nxt){
        int v = E[k].to;
        if(!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
        else if(ins[v]) low[u] = min(low[u], low[v]);
    }
    if(low[u] == dfn[u]){
        bcnt++; int pos = 0;
        while(pos ^ u) pos = stk[top--], ins[pos] = false, bel[pos] = bcnt;
    }
}

int main()
{
    freopen("_in.in", "r", stdin);

    n = read(), m = read();
    while(m--){
        int i = read(), a = read(), j = read(), b = read();
        if(a ^ b){
            if(a > b) swap(i, j), swap(a, b);
            add(i, j), add(j + n, i + n);
        }
        else{
            if(!a) add(i, j + n), add(j, i + n);
            else add(i + n, j), add(j + n, i);
        }
    }

    for(int i = 1; i <= (n << 1); i++) if(!dfn[i]) dfs(i);
    
    bool flag = true;
    for(int i = 1; i <= n && flag; i++) flag &= (bel[i] != bel[i + n]);

    if(!flag) puts("IMPOSSIBLE");
    else{
        puts("POSSIBLE");
        for(int i = 1; i <= n; i++) if(bel[i] < bel[i + n]) printf("1 "); else printf("0 ");
    }
}