uvalive 4452 2-sat

/**
这题，参考别人的代码。
理解2-sat吧，就是在题目给出的条件中，假设某个条件成立，会得出什么样的结论，相应的在图中连边，然后可以判断各种情况可不可行
然后学习了，当确定选择某中状态A时，从它的对立状态A^1引一条边add(A^1,A)，从而使凡是dfs经过对立状态，必然return false；即保证若存在一种可能性，必然是经过该状态A的。
这题，如果一个人投票数小于等于2，必须成立。
如果大于2，若其中一个不成立，其他的必须成立。
就根据这两个条件连边，最后判断。
**/


#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=1005;

struct TwoSAT
{
   int n,c;
   vector<int> G[maxn*2];
   bool mark[maxn*2];
   int S[maxn*2],res[105];

   bool dfs(int x)
   {
      if(mark[x^1]) return false;
      if(mark[x]) return true;
      mark[x]=true;
      S[c++]=x;
      for(int i=0;i<G[x].size();i++)
         if(!dfs(G[x][i])) return false;
      return true;
   }

   void init(int n)
   {
      this->n=n;
      for(int i=0;i<n*2;i++) G[i].clear();
      memset(mark,0,sizeof(mark));
   }

   void add_clause(int x,int xval,int y,int yval)
   {
      x=x*2+xval;
      y=y*2+yval;
      G[x].push_back(y);
   }

   bool solve()
   {
      for(int i=0;i<n*2;i+=2)
      {
         if(!mark[i] && !mark[i+1])
         {
            c=0;
            if(!dfs(i))
            {
               while(c>0) mark[S[--c]]=false;
               if(!dfs(i+1)) return false;
            }
         }
      }
      return true;
   }

   bool test()
   {
      int ans;
      for(int i=0;i<n;i++)
      {
         ans=0;
         memset(mark,0,sizeof(mark));
         add_clause(i,1,i,0);
         while(c>0) mark[S[--c]]=false;
         if(solve()) ans+=1;
         G[2*i+1].pop_back();

         memset(mark,0,sizeof(mark));
         add_clause(i,0,i,1);
         while(c>0) mark[S[--c]]=false;
         if(solve()) ans+=2;
         G[2*i].pop_back();

         if(ans==0) return false;
         else if(ans==1) res[i]=-1;
         else if(ans==2) res[i]=1;
         else if(ans==3) res[i]=0;
      }
      return true;
   }
};

TwoSAT solver;

struct voter
{
   int b,v;
}vote[505][5];

int main()
{
   int n,m,cnt,j,i,kase=0,k;
   char c;
   while(scanf("%d%d",&m,&n)!=EOF)
   {
      if(n==0 && m==0) break;
      solver.init(m);
      for(i=0;i<n;i++)
      {
         scanf("%d",&cnt);
         for(j=0;j<cnt;j++)
         {
            scanf("%d %c",&vote[i][j].b,&c);
            vote[i][j].b--;
            if(c==‘y‘) vote[i][j].v=1;
            else vote[i][j].v=0;
         }
         if(cnt<=2)
            for(j=0;j<cnt;j++) solver.add_clause(vote[i][j].b,vote[i][j].v^1,vote[i][j].b,vote[i][j].v);
         else
         {
            for(j=0;j<cnt;j++)
               for(k=0;k<cnt;k++)
               {
                  if(j==k) continue;
                  solver.add_clause(vote[i][j].b,vote[i][j].v^1,vote[i][k].b,vote[i][k].v);
               }
         }
      }
      memset(solver.res,0,sizeof(solver.res));
      printf("Case %d: ",++kase);

      if(!solver.test()) printf("impossible\n");
      else
      {
         for(i=0;i<m;i++)
         {
            if(solver.res[i]==0) printf("?");
            else if(solver.res[i]==1) printf("y");
            else if(solver.res[i]==-1) printf("n");
         }
         printf("\n");
      }
   }
   return 0;
}