2-sat板子

vector<int>e[maxn];
int n,m;
int inscc[maxn];
int low[maxn],dfn[maxn];
stack<int>stk;
int instk[maxn];
int tot,cnt;
vector<int>scc[maxn];void dfs(int u,int fa){low[u]=dfn[u]=++tot;stk.push(u);instk[u]=1;for(int v:e[u]){if(!dfn[v]){//树边dfs(v,u);low[u] =min(low[u],low[v]);}else if(instk[v]){//非树边low[u] = min(low[u],dfn[v]);}}if(dfn[u]==low[u]){++cnt;//处理非根节点while(stk.top()!=u){scc[cnt].pb(stk.top());inscc[stk.top()]=cnt;instk[stk.top()]=0;stk.pop();}//处理根节点scc[cnt].pb(stk.top());inscc[stk.top()]=cnt;instk[stk.top()]=0;stk.pop();}
}
void solve(){cin>>n>>m;rep(i,1,m){int idx,a,jdx,b;cin>>idx>>a>>jdx>>b;int x=idx,y=jdx;int nota= (a^1),notb =(b^1);e[x+nota*n].pb(y+b*n);e[y+notb*n].pb(x+a*n);}for(int i=1;i<=2*n;i++){if(inscc[i])continue;dfs(i,0);}for(int i=1;i<=n;i++){if(inscc[i]==inscc[i+n]){cout<<"IMPOSSIBLE"<<endl;return;}}cout<<"POSSIBLE"<<endl;for(int i=1;i<=n;i++){if(inscc[i]>inscc[i+n]){cout<<1<<' ';}else cout<<0<<' ';}cout<<endl;
}