本文主要是介绍2402. 2-SAT 问题（tarjan，2-SAT模板题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
活动 - AcWing
给定 n 个还未赋值的布尔变量 x1∼xn。
现在有 m 个条件，每个条件的形式为 “xi 为 0/1 或 xj 为 0/1 至少有一项成立”，例如 “x1 为 1 或 x3 为 0”、“x8 为 0 或 x4 为 0” 等。
现在，请你对这 n 个布尔变量进行赋值（0 或 1），使得所有 m 个条件能够成立。
输入格式
第一行包含两个整数 n,m。
接下来 m 行，每行包含四个整数 i,a,j,b，用来描述一个条件，表示 “xi 为 a 或 xj 为 b”。
输出格式
如果问题有解，则第一行输出 POSSIBLE，第二行输出 n 个整数表示赋值后的 n 个变量 x1∼xn 的值（0 或 1），整数之间用单个空格隔开。
如果问题无解，则输出一行 IMPOSSIBLE 即可。
如果答案不唯一，则输出任意一种正确答案即可。
数据范围
1≤n,m≤106,
1≤i,j≤n,
0≤a,b≤1
输入样例：
3 2
1 1 3 1
2 0 3 0
输出样例：
POSSIBLE
1 1 0解析：
该文件无法打开 - AcWing
2-SAT 通常解决这样一类问题：给出若干个这样的命题 x1∼xn，给出一些条件 xi∪xj，即 xi 或 xj 为真，给所有的命题判断真假
首先，有如下等价关系：x∪y⇔¬x→y⇔¬y→x，则将 x 和 ¬x 看成两个不同的节点，将 ¬x 向 y
连边，¬y 向 x 连边，即如果 ¬x 为真的话 y 也必须为真，¬y 为真的话 x 也必须为真，则这样的关系依赖图显然会形成一个有向图，将该有向图缩点后，在一个强连通分量内判断是否存在这样一条 x→¬x，即如果 x 为真的话 ¬x 也必然为真，显然矛盾，即整个命题无解，否则 是否一定有解
用 Tarjan 算法求强联通分量，检查是否存在 i 和 i + N 在同一个强连通分量即可。本题还需要输出方案。
这里给出 2-SAT 合法方案的两种构造方法。
第一种构造方法
首先，在一个强连通分量中，只要确定了一个变量的赋值，该强连通分量内其他变量的赋值也就直接确定了，
这启发我们考虑缩点，其次，因为互为逆否命题的有向边在图中成对出现，所以一个零出度点对面的点一定有出边。
选择一个有出边的店会使得该边指向的点必须也被选择，而选择一个零出度点则不会对其他任何点造出影响。
根据上述讨论，第一种构造方法的基本思想就是：自底向上执行拓扑排序，不断尝试选择零出度点。
1. 把强连通分量缩点，因为一般的拓扑排序是自顶向下根据入度进行的，所以我们建立一张缩点后的反图，具体来说：
(1) 图上每个点都对应原图的强连通分量
(2) 原图中的边 (x, y) 转化为新图中的边 (c[y], c[x])，其中 c[x] != c[y]，c[x] 表示节点 x 所在的强连通分量
(3) 对于原图中每个点 x，c[x] 和 c[x + N] 新图中两个对称的节点。
2. 在上述反图上统计每个点的入度，执行拓扑排序
设val[k] 表示原图 k 号强连通分量的赋值标记，初始值为 -1
从队头每取出一个节点 k (k 相当于原图中一个强连通分量的编号)，就检查 k 的赋值标记，若 val[k] = -1 (尚未确定赋值)，
就令 val[k] = 0， val[k + N] = 1，随后把它能到达的点的入度减 1 (拓扑排序的正常过程)
3. 拓扑排序结束之后，就得到最终的答案，对于原图每个节点 i：
若 val[c[i]] = 0，则变量 x[i] 应赋值为 x[i][0]
若 val[c[i]] = 1，则变量 x[i] 应赋值为 x[i][1]
第二种构造方法
第二种构造方法是基于第一种构造方法的基础上，进一步利用了 Tarjan 算法对强连通分量编号的特殊性质，使得构造过程更简洁。
可以发现 Tarjan 算法的本质是一次 dfs，它在回溯时会先取出有向图底部的强连通分量进行标记，所以 Tarjan 算法得到的强连
通分量编号本身就已经满足缩点后有向无环图中自底向上的顺序，序列 1, 2, ..., cnt 就是缩点后的反图的拓扑序，无需进行拓
扑排序。
因此，直接比较节点所在的强连通分量的编号大小，即可确定对应变量的赋值 val[i]，c[i] 和 c[i + N] 哪个小，就表示哪个会
先被遍历到，先被遍历到的是取值为 0，后被遍历到的取值为 1。
最终，同样的枚举一遍所有节点，根据 val[i] 来确定每个节点的值。
注：构造方法2 其实等于是 构造方法1 的升级版
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e6+10, M = 2e6+ 10, INF = 0x3f3f3f3f;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts;
int stk[N], top;
bool in_stk[N];
int id[N],cnt;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}int tarjan(int u) {dfn[u] = low[u] = ++ts;stk[++top] = u, in_stk[u] = 1;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (!dfn[j]) {tarjan(j);low[u] = min(low[u], low[j]);}else if (in_stk[j]) {low[u] = min(low[u], dfn[j]);}}if (dfn[u] == low[u]) {int y;cnt++;do {y = stk[top--];in_stk[y] = 0;id[y] = cnt;} while (y != u);}
}int main() {cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1,x,a,y,b; i <= m; i++) {scanf("%d%d%d%d", &x, &a, &y, &b);x--, y -- ;add(2 * x + !a, 2 * y + b);add(2 * y + !b, 2 * x + a);}for (int i = 0; i < 2 * n; i++) {if (!dfn[i])tarjan(i);}for (int i = 0; i < n; i++) {if (id[i * 2] == id[2 * i + 1]) {cout << "IMPOSSIBLE" << endl;return 0;}}cout << "POSSIBLE" << endl;for (int i = 0; i < n; i++) {if (id[i * 2] < id[i * 2 + 1])printf("0 ");else printf("1 ");}return 0;
}这篇关于2402. 2-SAT 问题（tarjan，2-SAT模板题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
