【luogu P4782】【模板】2-SAT 问题

【模板】2-SAT 问题

题目链接：luogu P4782

题目大意

2-SAT 模板题，有一些条件，要求想发生的某两个事件至少发生一个。
问你有没有可能全部条件都满足，如果有，输出表示可以的字符串，并且输出一种事件的发生方案。如果没有，就输出表示不可以的字符串。

思路

之前写过，可以看之前的博客。
——>这个是看如何判断条件是否都能成立（第一部分）<——
——>这个是看如何求出一个合法的事件发生方案（第二部分）<——

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

struct node {
	int to, nxt;
}e[4000001];
int n, m, x, y, le[2000001], KK, cx, cy;
int dfn[2000001], low[2000001], tmp;
int sta[2000001], in[2000001], n_n;

void add(int x, int y) {
	e[++KK] = (node){y, le[x]}; le[x] = KK;
}

int another(int x) {
	if (x > n) return x - n;
	return x + n;
}

void tarjan(int now) {
	dfn[now] = low[now] = ++tmp;
	sta[++sta[0]] = now;
	
	for (int i = le[now]; i; i = e[i].nxt)
		if (!dfn[e[i].to]) {
			tarjan(e[i].to);
			low[now] = min(low[now], low[e[i].to]);
		}
		else if (!in[e[i].to]) low[now] = min(low[now], low[e[i].to]);
	
	if (dfn[now] == low[now]) {
		in[now] = ++n_n;
		while (sta[sta[0]] != now) {
			in[sta[sta[0]]] = n_n;
			sta[0]--;
		}
		sta[0]--;
	}
	
	return ;
}

int main() {
	scanf("%d %d", &n, &m);
	
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d %d", &x, &cx, &y, &cy);
		if (!cx) x += n;
		if (!cy) y += n; 
		add(x, another(y));
		add(y, another(x));
	}
	
	for (int i = 1; i <= 2 * n; i++)
		if (!dfn[i]) tarjan(i);
	
	for (int i = 1; i <= n; i++)
		if (in[i] == in[n + i]) {
			printf("IMPOSSIBLE
");
			return 0;
		}
	
	printf("POSSIBLE
");
	for (int i = 1; i <= n; i++) {
		if (in[i] > in[i + n]) printf("1 ");
			else printf("0 ");
	}
	
	return 0;
}