2-Sat+输出可行解(个人模版)

2-Sat+输出可行解：

 //LightOJ 1251

 #include<stdio.h>

 #include<string.h>

 #include<vector>

 #include<queue>

 using namespace std;

 int output[];

 int vis[];

 int low[];

 int dfn[];

 int print[];

 int stack[];

 int color[];

 int pos[];

 int degree[];

 vector<int >mp[];

 vector<int >mp2[];

 int n,m,sig,cnt,tot,cont;

 void add(int x,int y)

 {

     mp[x].push_back(y);

 }

 void top()

 {

     memset(print,,sizeof(print));

     queue<int >s;

     for(int i=;i<=sig;i++)

     {

         if(degree[i]==)

         {

             s.push(i);

         }

     }

     while(!s.empty())

     {

         int u=s.front();

         if(print[u]==)

         {

             print[u]=;print[pos[u]]=;

         }

         s.pop();

         for(int i=;i<mp2[u].size();i++)

         {

             int v=mp2[u][i];

             degree[v]--;

             if(degree[v]==)s.push(v);

         }

     }

     cont=;

     for(int i=;i<=n;i++)if(print[color[i]]==)output[cont++]=i;

 }

 void Tarjan(int u)

 {

     vis[u]=;

     dfn[u]=low[u]=cnt++;

     stack[++tot]=u;

     for(int i=;i<mp[u].size();i++)

     {

         int v=mp[u][i];

         if(vis[v]==)Tarjan(v);

         if(vis[v]==)low[u]=min(low[u],low[v]);

     }

     if(low[u]==dfn[u])

     {

         sig++;

         do

         {

             vis[stack[tot]]=-;

             color[stack[tot]]=sig;

         }

         while(stack[tot--]!=u);

     }

 }

 int Slove()

 {

     sig=;

     cnt=;

     tot=-;

     memset(degree,,sizeof(degree));

     memset(stack,,sizeof(stack));

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

     memset(vis,,sizeof(vis));

     memset(color,,sizeof(color));

     for(int i=;i<=n*;i++)

     {

         if(vis[i]==)

         {

             Tarjan(i);

         }

     }

     for(int i=;i<=n;i++)

     {

         if(color[i]==color[i+n])return ;

         pos[color[i]]=color[i+n];

         pos[color[i+n]]=color[i];

     }

     for(int i=;i<=n*;i++)

     {

         for(int j=;j<mp[i].size();j++)

         {

             int v=mp[i][j];

             if(color[i]!=color[v])

             {

                 degree[color[i]]++;

                 mp2[color[v]].push_back(color[i]);

             }

         }

     }

     top();

     return ;

 }

 int main()

 {

     int t;

     int kase=;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&m,&n);

         for(int i=;i<=;i++)mp[i].clear(),mp2[i].clear();

         for(int i=;i<m;i++)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             int xx=x;int yy=y;

             if(x<)x=-x;

             if(y<)y=-y;

             if(xx>&&yy>)add(x+n,y),add(y+n,x);

             if(xx>&&yy<)add(x+n,y+n),add(y,x);

             if(xx<&&yy>)add(x,y),add(y+n,x+n);

             if(xx<&&yy<)add(x,y+n),add(y,x+n);

         }

         int ans=Slove();

         printf("Case %d: ",++kase);

         if(ans==)

         {

             printf("Yes\n");

             printf("%d",cont);

             for(int i=;i<cont;i++)

             {

                 printf(" %d",output[i]);

             }

             printf("\n");

         }

         else printf("No\n");

     }

 }