速通2-SAT

yyrwlj · 2024-01-08 18:36:55 · 个人记录

种类并查集都会吧？2-SAT就是变成了在图上找环

所以加边也差不多，稍微麻烦亿点：

if (va && vb) { // a, b 都真，-a -> b, -b -> a
    g[a + n].push_back(b);
    g[b + n].push_back(a);
} else if (!va && vb) { // a 假 b 真，a -> b, -b -> -a
    g[a].push_back(b);
    g[b + n].push_back(a + n);
} else if (va && !vb) { // a 真 b 假，-a -> -b, b -> a
    g[a + n].push_back(b + n);
    g[b].push_back(a);
} else if (!va && !vb) { // a, b 都假，a -> -b, b -> -a
    g[a].push_back(b + n);
    g[b].push_back(a + n);
}

但是可以优化一下：

add(a + n * (va & 1), b + n * (vb ^ 1));
add(b + n * (vb & 1), a + n * (va ^ 1));

然后tarjan缩点，有 id[i] == id[i + n] 就无解。

输出答案就是：

for (int i=1;i<=n;i++)
    printf("%d ", id[i] < id[i + n]);