作用
给 \(n\) 个布尔变量，有 \(m\) 个限制形如：\(i\) 变量为真，则 \(j\) 变量为假、\(i\) 变量为真，则 \(j\) 变量为真……
求出每个布尔变量的值，使得满足所有限制，或者报告无解。
做法
形如上述的限制，可以建一条 \(i\to j\) 的边，表示一个限制。
但是一个变量可以有 \(0\)、\(1\) 两种值，所以不妨对一个变量 \(i\) 拆成 \(i\) 与 \(i+n\) 两个点，分别表示取 \(0\) 和取 \(1\)。
建完边后，直接说结论：
一、对于一个变量 \(i\)，如果图中有一条 \(i\to i+n\) 的路径，而没有 \(i+n\to i\) 的路径，那么变量 \(i\) 取 \(0\) 就不合法，而取 \(1\) 就合法，反之。如果 \(i\to i+n\) 与 \(i+n\to i\) 的路径都没有，任意取一个即可。
二、对于一个变量 \(i\)，如果图中同时存在 \(i\to i+n\) 与 \(i+n\to i\) 这两条路径，则无解。
知道这个后跑一个 Tarjan，求出每个点所属的强连通编号，记做 \(id\)。
把上述两条结论用代码翻译就是：
一、对于变量 \(i\)，如果 \(id_i\lt id_{i+n}\)，那么变量 \(i\) 取 \(0\) 合法，取 \(1\) 不合法，反之。在 Tarjan 中，强连通编号小的点是一定不能到大强连通大的点的。
二、对于变量 \(i\)，如果 \(id_i=id_{i+n}\) 那么无解。
细节
2-SAT 只能做 \(A\) 则 \(B\) 的限制，如果要做 \(A\) 或 \(B\) 的限制，就需要处理一下。
例如，\(i\) 真或 \(j\) 假这条限制，可以变成 \(i\) 假则 \(j\) 假、\(j\) 真则 \(i\) 真这两条限制。
例题。
#include <bits/stdc++.h>void Freopen() {freopen("", "r", stdin);freopen("", "w", stdout);
}using namespace std;
const int N = 2e6 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;int n, m;
vector< int> G[N], sta;int tot, cnt;
int dfn[N], low[N], vis[N], col[N];void tarjan( int u) {sta.push_back(u), vis[u] = 1;dfn[u] = low[u] = ++ tot;for ( auto v : G[u]) {if (! dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);else if (vis[v]) low[u] = min(low[u], dfn[v]);}if (dfn[u] != low[u]) return ;int v; ++ col[0];do {v = sta.back(); sta.pop_back(), vis[v] = 0;col[v] = col[0];} while (v != u) ;
}signed main() {ios :: sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;while (m --) {int i, a, j, b;cin >> i >> a >> j >> b;if (a && b) G[i].push_back(j + n), G[j].push_back(i + n);if (! a && ! b) G[i + n].push_back(j), G[j + n].push_back(i);if (! a && b) G[i + n].push_back(j + n), G[j].push_back(i);if (a && ! b) G[i].push_back(j), G[j + n].push_back(i + n);}for ( int i = 1; i <= 2 * n; i ++)if (! dfn[i]) tarjan(i);for ( int i = 1; i <= n; i ++)if (col[i] == col[i + n]) cout << "IMPOSSIBLE\n", exit(0);cout << "POSSIBLE\n";for ( int i = 1; i <= n; i ++)if (col[i] < col[i + n]) cout << "0 ";else cout << "1 ";return 0;
}