洛谷4782 【模板】2-SAT 问题

原题链接

\(2-SAT\)模板

#include<cstdio>
using namespace std;
const int N = 2e6 + 10;
int fi[N], di[N], ne[N], dfn[N], low[N], st[N], bl[N], l, tp, ti, SCC;
bool v[N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline void add(int x, int y)
{
    di[++l] = y;
    ne[l] = fi[x];
    fi[x] = l;
}
inline int minn(int x, int y)
{
    return x < y ? x : y;
}
void tarjan(int x)
{
    int i, y;
    dfn[x] = low[x] = ++ti;
    st[++tp] = x;
    v[x] = 1;
    for (i = fi[x]; i; i = ne[i])
    {
        y = di[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = minn(low[x], low[y]);
        }
        else
            if (v[y])
                low[x] = minn(low[x], dfn[y]);
    }
    if (!(dfn[x] ^ low[x]))
    {
        ++SCC;
        do
        {
            y = st[tp--];
            bl[y] = SCC;
            v[y] = 0;
        } while (x ^ y);
    }
}
int main()
{
    int i, n, m, x, y, a, b;
    n = re();
    m = re();
    for (i = 1; i <= m; i++)
    {
        x = re();
        a = re();
        y = re();
        b = re();
        add(x + (a ^ 1) * n, y + b * n);
        add(y + (b ^ 1) * n, x + a * n);
    }
    for (i = 1; i <= (n << 1); i++)
        if (!dfn[i])
            tarjan(i);
    for (i = 1; i <= n; i++)
        if (!(bl[i] ^ bl[i + n]))
        {
            printf("IMPOSSIBLE");
            return 0;
        }
    printf("POSSIBLE\n");
    for (i = 1; i <= n; i++)
        printf("%d ", bl[i] > bl[i + n]);
    return 0;
}

洛谷4782 【模板】2-SAT 问题

原文：https://www.cnblogs.com/Iowa-Battleship/p/9634209.html