2_sat

要求字典序的情況的話，爆搜

不要求的話

1:建圖，有向邊A--->B的意義為選擇A則必須選擇B，一般一個點的兩種取值情況會拆點。

2:縮點。

3:建反向圖，跑拓撲排序（有說不用建再跑，但我不懂為什么）。

4：根據實際情況輸出。

例題：https://www.luogu.org/problemnew/show/P4782

代碼

#include<cstdio>
#include<ctype.h>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long
inline ll rd()
{ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;
}
const int N=2e6+13;
vector<int>g[N];
struct zx{int nx,to;}e[N<<1];
int dfn[N],low[N],top,num,nm,cnt,a[N],v[N],bj[N],du[N],h[N],opp[N];
void TJ(int x)
{dfn[x]=low[x]=++num;a[++top]=x;for(int i=0,y;i<g[x].size();i++) if(!dfn[y=g[x][i]]) TJ(y),low[x]=min(low[x],low[y]);else if(!v[y]) low[x]=min(low[x],dfn[y]);if(low[x]!=dfn[x]) return ;v[x]=++cnt;while(a[top]!=x) v[a[top--]]=cnt;top--;
}
void add(int x,int y){e[++nm]={h[x],y};h[ax]=nm;du[y]++;}
int main()
{int n=rd(),m=rd(),i,c,b,j,l=0,r=0,x,y;for(int k=1;k<=m;k++)  i=rd(),c=rd(),j=rd(),b=rd(),g[i<<1|c].push_back(j<<1|(!b)),g[j<<1|b].push_back(i<<1|(!c));for(i=2;i<=(n<<1|1);i++) if(!dfn[i]) TJ(i);for(x=2;x<=(n<<1|1);x++) for(i=0;i<g[x].size();i++) if(v[g[x][i]]!=v[x]) add(v[g[x][i]],v[x]);for(i=1;i<=n;i++)if(v[i<<1]==v[i<<1|1]){printf("IMPOSSIBLE");return 0;}for(i=2;i<=(n<<1|1);i++) opp[v[i]]=v[i^1];for(int i=1;i<=cnt;i++) if(!du[i]) a[r++]=i;while(l<r){x=a[l++];bj[x]=1;bj[opp[x]]=-1;for(i=h[x];i;i=e[i].nx) if(!--du[y=e[i].to]&&!bj[y]) a[r++]=y;}printf("POSSIBLE\n");for(int i=1;i<=n;i++) if(bj[v[i<<1]]==1)printf("1 ");else printf("0 ");return 0;
}

?