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 问题的模板题，对于每个条件 a∧b，得出推导公式 −a→b 和 −b→a，按照推导公式建图，然后求强连通分量并进行缩点，如果任意一个变量的两种取值在同一个强连通分量中，说明无解。否则枚举每个变量，选取所在强连通分量拓扑序靠后的取值。

#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;
}