2-SAT

问题描述：

有 $n$ 个 bool 变量，有$m$个条件，如 $\lfloor x_i$ 为 true/flase 或 $x_j$ 为 true/false $\rfloor$。求是否有方案能满足所有条件。构造出一组符合题意的解。

算法思路：

按照条件建立分层图，令 $x_i$ 为 true，$x_{i+n}$ 为 false。

举个例子，设有条件 $\lfloor x_i$ 为 flase 或 $x_j$ 为 true $\rfloor$。则当 $x_i$ 为 true 时，$x_j$ 必定为 true。当 $x_j$ 为 false时，$x_i$ 必定为 false。

此时建立有向边 $x_i \rightarrow x_j$，$x_{j + n} \rightarrow x_{i+n}$。当箭头左边条件成立时，右边条件一定成立。但注意，右边条件成立时，左边条件不一定成立。这也是建立有向边而非无向边的原因。

建完所有边后，跑 Tarjan，如果发现 $x_i$ 与 $x_{i+n}$ 在同一强连通分量，即条件两两等价，此时矛盾，问题无解。

若有解，$x_i$ 与 $x_{i+n}$ 的拓扑序更大的即是 $i$ 的解。

注意 Tarjan 的 feature，代码实现中解为 $color_i$ 值更小的点。

模板传送门

#include <bits/stdc++.h>
#define rei register int
#define N 4000005
using namespace std;
typedef long long LL;
typedef unsigned long long ull;

int n, m, dfn[N], low[N], cnt, co[N], st[N], top, col;
vector<int> g[N];

struct edge
{
    int v, nxt;
} e[N];

template <typename T> inline void read(T &x)
{
    x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    x *= f;
}

inline void Tarjan(int x)
{
    dfn[x] = low[x] = ++cnt;
    st[++top] = x;
    for (rei i = 0; i < g[x].size(); i++)
    {
        int v = g[x][i];
        if (!dfn[v])
        {
            Tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if (!co[v])
            low[x] = min(low[x], dfn[v]);
    }
    if (low[x] == dfn[x])
    {
        co[x] = ++col;
        while (st[top] != x)
        {
            co[st[top]] = col;
            top--;
        }
        top--;
    }
}

int main()
{
    read(n); read(m);
    for (rei i = 1; i <= m; i++)
    {
        int j, a, k, b;
        read(j); read(a); read(k); read(b);
        g[j + n * (a & 1)].push_back(k + n * (b ^ 1));
        g[k + n * (b & 1)].push_back(j + n * (a ^ 1));
    }
    for (rei i = 1; i <= n * 2; i++)
        if (!dfn[i]) Tarjan(i);
    for (rei i = 1; i <= n; i++)
    {
        if (co[i] == co[i + n])
        {
            printf("IMPOSSIBLE\n");
            return 0;
        }
    }
    printf("POSSIBLE\n");
    for (rei i = 1; i <= n; i++)
    {
        int res = co[i] < co[i + n];
        printf("%d ", res);
    }
    return 0;
}