[洛谷P4782]【模板】2-SAT 问题

题目大意：有$n$个布尔变量 $x_1 sim x_n$，另有$m$个需要满足的条件，每个条件的形式都是"$x_i$ 为$true/false$或$x_j$为$true/false$"。比如"$x_1$为$true$或$x_3$为$false$"、"$x_7$为$false$或$x_2$为$false$"。$2-SAT$问题的目标是给每个变量赋值使得所有条件得到满足。

题解：$2-SAT$，若$a$推出$b$，就连两条边，分别为$a -> b$和$!b -> !a$，若$a$一定为$true$，就连一条$!a -> a$（$false$相同），然后$tarjan$缩点，若一个点的两个状态在同一个强连通分量中，就有矛盾，否则那一个状态先访问到就为什么状态

卡点：1.$tarjan$缩点弹出栈时条件写错

C++ Code：

#include <cstdio>
#define maxn 1000010 << 1
using namespace std;
int n, m;
int head[maxn], cnt;
struct Edge {
	int to, nxt;
} e[maxn];
void add(int a, int b) {
	e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;
}
int low[maxn], DFN[maxn], stack[maxn], res[maxn], tot, idx, CNT;
bool vis[maxn];
inline int min(int a, int b) {return a < b ? a : b;}
void tarjan(int rt) {
	DFN[rt] = low[rt] = ++idx;
	vis[stack[++tot] = rt] = true;
	int v;
	for (int i = head[rt]; i; i = e[i].nxt) {
		v = e[i].to;
		if (DFN[v]) {
			if (vis[v]) low[rt] = min(low[rt], DFN[v]);
		} else {
			tarjan(v);
			low[rt] = min(low[rt], low[v]);
		}
	}
	if (DFN[rt] == low[rt]) {
		CNT++;
		do {
			vis[v = stack[tot--]] = false;
			res[v] = CNT;
		} while (rt != v);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		add(a << 1 | !b, c << 1 | d);
		add(c << 1 | !d, a << 1 | b);
	}
	for (int i = 2; i <= (n << 1 | 1); i++) {
		if (!DFN[i]) tarjan(i);
	}
	for (int i = 1; i <= n; i++) {
		if (res[i << 1] == res[i << 1 | 1]) {
			puts("IMPOSSIBLE");
			return 0;
		}
	}
	puts("POSSIBLE");
	for (int i = 1; i <= n; i++) printf("%d ", res[i << 1] > res[i << 1 | 1]);
	puts("");
	return 0;
}