2-sat模板

给定n个变量 给定m对关系 例如 aVb !aVb 让你构造出一组布尔值解满足题目要求
就是2sat的模板 把拓扑序后面的点当做可行解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---\n");
const int N=2000010,M=2000010;
int h[N],ne[M],e[M],idx,top,id[N],dfn[N],low[N],stk[N];
bool instk[N];
void add(int a,int b)
{
   
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
int stp;
int cnt;
void tarjin(int u)
{
   
	dfn[u]=low[u]=++stp;
	instk[u]=true,stk[++top]=u;
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(!dfn[j])
		{
   
		tarjin(j);
		low[u]=min(low[u],low[j]);
		}
		else if(instk[j])
		low[u]=min(low[u],dfn[j]);		
	}
	if(low[u]==dfn[u])
	{
   
		++cnt;
		int y;
		do
		{
   
			y=stk[top--];
			instk[y]=false;
			id[y]=cnt;
		}while(y!=u);
	}
}
int main()
{
   	
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	while(m--)
	{
   
		int i,a,j,b;
		scanf("%d%d%d%d",&i,&a,&j,&b);
		add(2*i+!a,2*j+b);
		add(2*j+!b,2*i+a);
	}
	for(int i=2;i<=n*2+1;i++)
	{
   
		if(!dfn[i])
		tarjin(i);
	}
	for(int i=1;i<=n;i++)
	{
   
		if(id[i*2]==id[i*2+1]){
   
			puts("IMPOSSIBLE");
			return 0;
		}
	}
	puts("POSSIBLE");
	for(int i=1;i<=n;i++)
	{
   
		if(id[i*2]<id[i*2+1])
		printf("0 ");
		else
		printf("1 ");
	}
	puts("");
	return 0;
}