(模板)2-SAT

(模板)2-SAT

題目描述

有n個變數，m條語句，沒個形如：xi為a或xj為b(a,b=0或1)...

判斷是否有解，有的話構造出來一組解

思路:

• 將每個變數分為兩個點，取0和取1(i和i+n)
• 對於每條語句可以轉換為若xi取(1-a)則xj必須取b，若xj取(1-b)則xi必須取a,按照這樣的關係連邊
• 跑一遍tarjan，則在同一個強連通分量中如果取了一個點，那麼一定要取其中的其他的點，如果i與i+n在同一個強連通分量，則一定無解
• 有解時，先縮點，然後每次找到出度為0的點，選取它，並刪除即可，這樣得到的操作序列就相當於倒著跑一遍拓撲排序(因為拓撲排序是先找入度為0的點)
• 又註意到tarjan後的col數組其實就是一個自底向上的拓撲序,所以我們每次選出度最小的點就相當於選col小的點

代碼:

#include <cstdio>
#include <stack>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;

#define res register int
inline int read()
{
	int x=0,f=1; char ch;
	while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

const int N=4e6+5,M=4e6+5;
int head[N],fron[M],ver[M],nxt[M];
int tot,n,m;

inline void add(int x,int y)
{
	ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot;
}

int dfn[N],low[N],col[N],colnum,num;
bool ins[N];
stack <int> s;

void tarjian(int x)
{
	dfn[x]=low[x]=++num;
	s.push(x); ins[x]=1;
	for(res i=head[x],y ; i ; i=nxt[i])
		if(!dfn[y=ver[i]])
			tarjian(y),low[x]=min(low[x],low[y]);
		else 
			if(ins[y])
				low[x]=min(low[x],dfn[y]);
	if(dfn[x]==low[x])
	{
		++colnum; int y;
		do { 
			y=s.top(); s.pop();
			ins[y]=0; col[y]=colnum;
		}while(x!=y);
	}
}

// xi=xj-> yi=yj

int opp[N];
inline void work()
{
	for(res i=1 ; i<=n*2 ; ++i)
		if(!dfn[i]) tarjian(i);
		
	for(res i=1 ; i<=n ; ++i) 
	{
		if(col[i]==col[n+i]) 
		{
			puts("IMPOSSIBLE"); 
			return;
		}
	}
	puts("POSSIBLE");
	for(res i=1 ; i<=n ; ++i)
		printf("%d ", col[i] > col[i+n]);//col[i]<col[i+n]時選i->取0
}

int main()
{
	n=read(); m=read();
	for(res i=1 ; i<=m ; ++i)
	{
		int a=read(),b=read(),c=read(),d=read();
		// a=b^1 -> c=d
		// c=d^1 -> a=b
		add(a+(b^1)*n,c+d*n); add(c+(d^1)*n,a+b*n);
	}
	work();
	return 0;
}