趁此机会学了一下2-SAT。

以前的2-SAT都是用并查集写的，只能应用于极小的一部分情况，这次学了一正式的2-SAT，是用一张有向图来表示其依赖关系。

2-SAT的介绍参见刘汝佳《训练指南》。

1 /************************************************************** 2     Problem: 2199 3     User: zhuohan123 4     Language: C++ 5     Result: Accepted 6     Time:140 ms 7     Memory:1388 kb 8 ****************************************************************/ 9  10 #include 
     
      11 #include 
      
       12 #include 
       
        13 #include 
        
         14 using namespace std;15 int n,m;16 struct point{
   int y,n;}p[1100];int pnum;17 int head[2100];18 struct edge{
   int next,to;}g[11000];int gnum;19 void addedge(int from,int to)20 {21     g[++gnum].to=to;g[gnum].next=head[from];head[from]=gnum;22 }23 int q[2100],l,r;24 bool cango[2100];25 bool check(int po)26 {27     memset(cango,0,sizeof cango);28     cango[po]=true;l=1;r=0;q[++r]=po;29     while(l<=r)30         for(int i=head[q[l++]];i;i=g[i].next)31             if(!cango[g[i].to])cango[q[++r]=g[i].to]=true;32     for(int i=1;i<=n;i++)33         if(cango[p[i].y]&&cango[p[i].n])return false;34     return true;35 }36 char ans[1100];37 int main(int argc, char *argv[])38 {39     #ifndef ONLINE_JUDGE40         freopen("1.in","r",stdin);41         freopen("1.out","w",stdout);42     #endif43     scanf("%d%d",&n,&m);44     for(int i=1;i<=n;i++)p[i].n=++pnum,p[i].y=++pnum;45     while(m--)46     {47         int b,c;char vb[4],vc[4];48         scanf("%d%s%d%s",&b,vb,&c,vc);49         if(vb[0]=='Y'&&vc[0]=='Y')addedge(p[b].n,p[c].y),addedge(p[c].n,p[b].y);50         if(vb[0]=='Y'&&vc[0]=='N')addedge(p[b].n,p[c].n),addedge(p[c].y,p[b].y);51         if(vb[0]=='N'&&vc[0]=='Y')addedge(p[b].y,p[c].y),addedge(p[c].n,p[b].n);52         if(vb[0]=='N'&&vc[0]=='N')addedge(p[b].y,p[c].n),addedge(p[c].y,p[b].n);53     }54     for(int i=1;i<=n;i++)55     {56         bool by=check(p[i].y),bn=check(p[i].n);57         if(by&&bn)ans[i]='?';58         else if(by)ans[i]='Y';59         else if(bn)ans[i]='N';60         else {puts("IMPOSSIBLE");return 0;}61     }62     puts(ans+1);63     return 0;64 }
        
       
      
     

P.S.这个代码写的相当非主流啊！