[数据结构与算法]2-SAT 问题【模板】

>Link

lugou P4782

>Description

>解题思路

2-SAT问题如题目所示。
注意到每个变量只能为真或假，也就是同一个变量真和假不能同时存在。
我们可以根据题目要求满足的条件建图，把每个变量分成真假两个点，按照条件建边，比如 「$x_1$为真或 $x_3$为假」，就建一条边 $(x_{1}real,x_{3}real)$，表示起点可以推出终点。
无解的情况就是同一个变量的真假互相推出了（注意是互相），可以用tarjan判强连通分量判断

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#define N 2000010
using namespace std;

stack<int> st;
struct edge
{
	int to, nxt;
} e[N], ee[N];
int n, m, low[N], dfn[N], tot, col[N], totcol, cnt, h[N];

void add (int u, int v)
{
	e[++cnt] = (edge){v, h[u]};
	h[u] = cnt;
}
void dfs (int now)
{
	dfn[now] = low[now] = ++tot;
	st.push (now);
	int v;
	for (int i = h[now]; i; i = e[i].nxt)
	{
		v = e[i].to;
		if (!dfn[v])
	  	{
	  		dfs (v);
	  		low[now] = min (low[now], low[v]);
	  	}
	  	else if (!col[v]) low[now] = min (low[now], low[v]);
	}
	if (dfn[now] == low[now])
	{
		col[now] = ++totcol;
		while (st.top() != now)
		{
			col[st.top()] = totcol;
			st.pop();
		}
		st.pop();
	}
}

int main()
{
	scanf ("%d%d", &n, &m);
	while (m--)
	{
		
		int a, b, i, j;
		scanf ("%d%d%d%d", &i, &a, &j, &b);
		add (i + a * n, j + (b ^ 1) * n);
		add (j + b * n, i + (a ^ 1) * n);
	}
	for (int i = 1; i <= n * 2; i++)
	  if (!dfn[i]) dfs (i);
	for (int i = 1; i <= n; i++)
	  if (col[i] == col[i + n])
	  {
	  	printf ("IMPOSSIBLE");
	  	return 0;
	  }
	printf ("POSSIBLE\n");
	for (int i = 1; i <= n; i++)
	  printf ("%d ", col[i] < col[i + n]);
	puts ("");
	return 0;
}