简述：给出 n 个法案， m 头牛的意见， 每头牛有两个表决 格式为 “支持或反对某法案”， 每头牛需要至少满足一个表决， 不可能成立的话输出 IMPOSSIBLE， 否则输出方案， Y代表能， N代表不能，若是有的解中法案可以通过， 有些不能则输出“？”

 

首先不难看出这是一个2-SAT问题

那么我们先建好图然后tarjan缩点

主要的问题就是如何判断一个法案是否在不同方案里有不同选择了

这个可以直接dfs，设$i$表示该法案通过，$i'$表示该法案不通过，那么在缩完点后的DAG上跑，看看从$i$能否到$i'$以及从$i'$能否到$i$，如果一个点能到另一个点，那么很明显该点代表的状态就不存在

如果两个都可以说明是$?$，否则的话只有一种方法可以

然而我数组开小TLE了……而且还只有一个点……搞得我还以为dfs的时间复杂度不对……

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 template
        
         inline bool cmin(T&a,const T&b){
   return a>b?a=b,1:0;} 7 inline int read(){ 8     #define num ch-'0' 9     char ch;bool flag=0;int res;10     while(!isdigit(ch=getchar()))11     (ch=='-')&&(flag=true);12     for(res=num;isdigit(ch=getchar());res=res*10+num);13     (flag)&&(res=-res);14     #undef num15     return res;16 }17 inline char getc(){18     char ch;while((ch=getchar())!='Y'&&ch!='N');return ch;19 }20 const int N=2005,M=10005;21 int head[N],Next[M],ver[M],tot;22 inline void add(int u,int v){23     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;24 }25 int hc[N],nc[M],vc[M],tc;26 inline void addc(int u,int v){27     vc[++tc]=v,nc[tc]=hc[u],hc[u]=tc;28 }29 int dfn[N],low[N],st[N],bl[N],num,cnt,top,n,m;30 void tarjan(int u){31     low[u]=dfn[u]=++num,st[++top]=u;32     for(int i=head[u];i;i=Next[i]){33         int v=ver[i];34         if(!dfn[v]) tarjan(v),cmin(low[u],low[v]);35         else if(!bl[v]) cmin(low[u],dfn[v]);36     }37     if(dfn[u]==low[u]) for(++cnt;st[top+1]!=u;--top) bl[st[top]]=cnt;38 }39 int dfs(int u,int g){40     if(u==g) return 0;41     for(int i=hc[u];i;i=nc[i])42     if(!dfs(vc[i],g)) return 0;43     return 1;44 }45 int main(){46 //    freopen("testdata.in","r",stdin);47     n=read(),m=read();48     for(int i=1;i<=m;++i){49         int a=read(),b=getc()=='Y',c=read(),d=getc()=='Y';50         add(a+(!b)*n,c+d*n),add(c+(!d)*n,a+b*n);51     }52     for(int i=1,l=n<<1;i<=l;++i) if(!dfn[i]) tarjan(i);53     for(int i=1;i<=n;++i)54     if(bl[i]==bl[i+n]) return puts("IMPOSSIBLE"),0;55     for(int u=1,l=n<<1;u<=l;++u)56     for(int i=head[u];i;i=Next[i])57     if(bl[u]!=bl[ver[i]]) addc(bl[u],bl[ver[i]]);58     for(int i=1;i<=n;++i){59         int a=dfs(bl[i],bl[i+n]),b=dfs(bl[i+n],bl[i]);60         if(a&&b) putchar('?');61         else if(a) putchar('N');62         else if(b) putchar('Y');63     }64     return 0;65 }