two-sat模板

P4782 【模板】2-SAT 问题

就是给关系进行连边，然后判断是否存在矛盾
输出方案的时候，就是在拓扑图上沿着反边走，但实际上tarjan求强连通分量已经排好序了
编号小的scc就是在拓扑序中排在后面的强连通分量

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))

using namespace std;
typedef double db;
typedef long long ll;
const int N =1e6+6;
int tot,head[N*2],nex[N*2],to[N*2];
int low[N*2],dfn[N*2],st[N*2],top,cnt,now,scc[N*2];
int n,m,x,y,a,b;
void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x){
	st[top++]=x;
	dfn[x]=low[x]=++now;
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (!dfn[v]){
			dfs(v);
			low[x]=min(low[x],low[v]);
		}
		else if (!scc[v]) low[x]=min(low[x],dfn[v]);
	}
	
	if (low[x]==dfn[x]){
		++cnt; int v;
		while (1){
			v=st[--top];
			scc[v]=cnt;
			if (x==v) break;
		}
	}
}
int main()
{
//	freopen("data.in","r",stdin);

	scanf("%d %d",&n,&m);
	fo(i,1,m){
		scanf("%d %d %d %d",&x,&a,&y,&b); 
		
		add(x+(1-a)*n, y+b*n);
		add(y+(1-b)*n, x+a*n);
	}
	
	fo(i,1,2*n) if (!dfn[i]) dfs(i);
	
	bool flag=1;
	fo(i,1,n) if (scc[i]==scc[i+n]) flag=0;
	if (!flag) puts("IMPOSSIBLE");
	else {
		puts("POSSIBLE");
		fo(i,1,n) printf("%d ",scc[i]>scc[i+n]);
	}
	
	return 0;
}