【模板】2-SAT

概念

何为2-SAT？

• 就是有n个位置，每个位置上要么0要么1。不可能同时存在i位置上既有0又有1。
• 有k个限制条件，在k个限制条件中满足 i 为 0/1 或者 j 为0/1。
• 在满足所有的限制条件的情况下是否能取出所有的i的情况。

限制条件

如何去解决限制条件？ 如果i为 1 或 j为0。并且要满足这个情况。那么 只要出现了i为0的时候，j就必须为1。推广来说，我们就可以理解为 ~vi 与 vj 有一条边、vi 与 ~vj 也有一条边。

建边

依据限制条件分析出来的结果，我们讲反向的值进行连边，表示：要使得条件成立，那么如果第一个条件不满足的话第二个条件必须满足

edge[ x+n*(vx&1) ].push_back( y+n*(vy^1) );
edge[ y+n*(vy&1) ].push_back( x+n*(vx^1) );

求解

1. 缩点 为什么是进行缩点？ 因为在有向图中，每一个点都是一个情况，而如果某个情况中出现了环，那表示取了其中任意一个情况后，环中的其余情况都必须取。
2. 遍历判断结果是否符合预期 对每个点继续遍历，看这个点的1和0的情况是否在同一环中，如果是，那么就是无解的。
3. 环的先后排序输出结果 如果结果符合预期，就可以输出一个可行的解了，这里使用的输出解的方式就是看环的先后，看1和0所在环的标号。

   for(int i=1;i<=n;i++)
   {
   printf( "%d ",cor[i]<cor[i+n] );
   }
   

注意事项

为了便于建图，i为i号取0，i+n为取真。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+12;
vector<int>edge[N];
int n,m,dfn[N],vis[N],low[N],cor[N],c,cnt,x,y,vx,vy,a,b;
stack<int>s;

void tarjan(int x)
{
  dfn[x]=low[x]=++cnt;
  s.push(x);
  vis[x]=1;
  for(auto y:edge[x])
  {
    if( !dfn[y] )
    {
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if( vis[y] ) low[x]=min(low[x],dfn[y]);
  }
  if( dfn[x]==low[x] )
  {
    c++;
    while( s.top()!=x )
    {
      int y=s.top();
      s.pop();
      cor[y]=c;
      vis[y]=0;
    }
    int y=s.top();
    s.pop();
    cor[y]=c;
    vis[y]=0;
  }
}

int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
  cin>>x>>vx>>y>>vy;
  edge[ x+n*(vx&1) ].push_back( y+n*(vy^1) );
  edge[ y+n*(vy&1) ].push_back( x+n*(vx^1) );
  }
  for(int i=1;i<=2*n;i++)
  {
    if( !dfn[i] ) tarjan(i);
  }

  for(int i=1;i<=n;i++)
  {
    if( cor[i]==cor[i+n] )
    {
      printf("IMPOSSIBLE");
      return 0;
    }
  }
  printf("POSSIBLE\n");
  for(int i=1;i<=n;i++)
  {
    printf( "%d ",cor[i]<cor[i+n] );
  }



}