P4782 【模板】2-SAT
大意
有 \(n\) 个布尔变量 \(c_1 \dots c_n\)，另有 \(m\) 个需要满足的条件，每个条件的形式都是\(「c_i = true / false\) 或 \(c_j = true/false」\)。
2-SAT问题的目标是给每个变量赋值使得所有条件得到满足。
思路
考虑二分图染色的方式。
每一个点只有选或不选两种情况，那么我们有这样的建图方式。
如果是 \(u = true\) \(\text{and}\) \(v = true\) 必须满足一个，那么就是 \(u\) 不选的话 \(v\) 必须选，\(v\) 不选的话 \(u\) 必须选。
因此我们 \(\neg u \to v\) 和 \(\neg v \to u\) 这样的连边方式。
于是剩下的情况类推，我们可以得到一个二分图。
只需要找到一种能刚好染色不冲突的方法，即为答案。
那么这样就可以得到 \(\mathcal{O}(nm)\) 的时间复杂度的玩意。
你可能会说，这时间复杂度可太烷氮了。
但是实际上这个复杂度能过很多 \(\text{2 - SAT}\) 的题目。
接下来考虑优化，我们想想刚刚那个二分图染色的过程，是不是相当于，如果我们直接缩点的话，缩完的点，只要你的 \(u\) 与 \(\neg u\) 不在一个 \(\text{SCC}\) 里面即可。
于是这个问题就解决了。
但是如果我们要用缩点的方式判断一个节点 \(u\) 到底是采用还是不采用，那么看 \(SCC[u]\) 和 \(SCC[\neg u]\) 在拓扑序的先后，显然在后面的为真。
代码
二分图染色写法：
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int n, m, S[N * 2], c;
bool selected[N * 2];
vector<int> g[N];bool dfs(int u){if(selected[u ^ 1]){return false;}if(selected[u]){return true;}selected[u] = true;S[c ++] = u;for(int i = 0;i < g[u].size();i ++){int v = g[u][i];if(!dfs(v)){return false;}}return true;
}bool Two_SAT(){for(int i = 0;i < 2 * n;i += 2){if(!selected[i] && !selected[i + 1]){c = 0;if(!dfs(i)){while(c > 0){selected[S[-- c]] = false;}if(!dfs(i + 1)){return false;}}}}return true;
}int main() {cin >> n >> m;for (int i = 0; i < m; i++) {int k, x, y;cin >> k >> x >> y;if(k == 0){g[2 * x].push_back(2 * x + 1);g[2 * y].push_back(2 * y + 1);}else{g[2 * x].push_back(2 * y + 1);g[2 * y].push_back(2 * x + 1);}}if (Two_SAT()) {cout << "YES";} else {cout << "NO";}return 0;
}
\(\text{Tarjan 缩点}\)
#include<iostream>
#include<vector>
#include<stack>
using namespace std;const int MAXN = 1e6 + 5;
const int NODE = 2 * MAXN;int n, m;
vector<int> g[NODE];
int dfn[NODE], low[NODE];
int scc[NODE];
bool ins[NODE];
stack<int> stk;
int tim = 0, cnt = 0;void targin(int u){low[u] = dfn[u] = ++ tim;stk.push(u);ins[u] = true;for(int &v : g[u]){if(!dfn[v]){targin(v);low[u] = min(low[u], low[v]);}else if(ins[v]){low[u] = min(low[u], dfn[v]);}}if(low[u] == dfn[u]){++ cnt;int v;do{v = stk.top();stk.pop();ins[v] = false;scc[v] = cnt;}while(v != u);}
}int main(){cin >> n >> m;for(int i = 1;i <= m;i ++){int u, a, v, b;cin >> u >> a >> v >> b;if(a == 1 && b == 1){g[u].push_back(v + n);g[v].push_back(u + n);}else if(a == 0 && b == 0){g[u + n].push_back(v);g[v + n].push_back(u);}else if(a == 1 && b == 0){g[u].push_back(v);g[v + n].push_back(u + n);}else{g[u + n].push_back(v + n);g[v].push_back(u);}}for(int i = 1;i <= 2 * n;i ++){if(!dfn[i]){targin(i);}}vector<int> ans;for(int i = 1;i <= n;i ++){if(scc[i] == scc[i + n]){cout << "IMPOSSIBLE\n";return 0;}ans.push_back((scc[i] > scc[i + n]));}cout << "POSSIBLE\n";for(int x : ans) cout << x << ' ';return 0;
}