第一道2sat，

其实2sat问题不难，只要记住一个：通过“推导出”连边

什么意思呢？就是一般题目中的变量都有两个状态，只能取一个，我们定义为true和false

对于每一个变量i，我们都拆成两个点，分别表示两种状态，设2i表示true，2i+1表示false。

然后来看每个条件，比如要满足xi=true or xj=true成立

显然，当xj=false,我们必然能推出xi=true,所以我们就连2j+1--->2i

同样的xi=false是，我们必然能推出xj=true,所以我们连2i+1--->2j

根据出这样的推导出关系我们就可以构建出一个图

如果能满足所有的条件，必然从任意变量的一个状态走，必定不能走到这个变量的对立状态

所以我们只要tarjan一下，判断任意2i，2i+1是否在一个强联通分量中，如果不存在，就说明能满足所有条件

这道题题目叙述很烦，只要掌握了基本的2sat问题，耐心分析一下是很容易做出的

1 type node=record  2        point,next:longint;  3      end;  4   5 var st,dfn,low,be,w:array[0..500] of longint;  6     edge:array[0..200010] of node;  7     v,f:array[0..500] of boolean;  8     tot,l,j,len,x,y,i,h,t,n,m,sum:longint;  9     f1,p,f2,flag:boolean; 10     s:string; 11  12 function min(a,b:longint):longint; 13   begin 14     if a>b then exit(b) else exit(a); 15   end; 16  17 function get(x,y:longint):longint; 18   var i:longint; 19   begin 20     if s[x]='m' then p:=false else p:=true; 21     get:=0; 22     for i:=x+1 to y do 23     begin 24       if s[i]=' ' then break; 25       get:=get*10+ord(s[i])-48; 26     end; 27   end; 28  29 procedure add(x,y:longint); 30   begin 31     inc(len); 32     edge[len].point:=y; 33     edge[len].next:=w[x]; 34     w[x]:=len; 35   end; 36  37 procedure tarjan(x:longint); 38   var i,y:longint; 39   begin 40     inc(h); 41     dfn[x]:=h; 42     low[x]:=h; 43     inc(t); 44     st[t]:=x; 45     f[x]:=true; 46     v[x]:=true; 47     i:=w[x]; 48     while i<>-1 do 49     begin 50       y:=edge[i].point; 51       if not v[y] then 52       begin 53         tarjan(y); 54         low[x]:=min(low[x],low[y]); 55       end 56       else if f[y] then low[x]:=min(low[x],low[y]); 57       i:=edge[i].next; 58     end; 59     if low[x]=dfn[x] then 60     begin 61       inc(sum); 62       while st[t+1]<>x do 63       begin 64         y:=st[t]; 65         f[y]:=false; 66         be[y]:=sum; 67         dec(t); 68       end; 69     end; 70   end; 71  72 begin 73   readln(tot); 74   while tot>0 do 75   begin 76     readln(n,m); 77     len:=0; 78     fillchar(w,sizeof(w),255); 79     for i:=1 to m do 80     begin 81       readln(s); 82       l:=length(s); 83       for j:=1 to l do 84         if s[j]=' ' then break; 85       x:=get(1,j-1); 86       f1:=p; 87       y:=get(j+1,l); 88       f2:=p; 89       if f1 and f2 then 90       begin 91         add(x+n,y); 92         add(y+n,x); 93       end 94       else if not f1 and not f2 then 95       begin 96         add(x,y+n); 97         add(y,x+n); 98       end 99       else if not f1 and f2 then100       begin101         add(x,y);102         add(y+n,x+n);103       end104       else if f1 and not f2 then105       begin106         add(x+n,y+n);107         add(y,x);108       end;109     end;110     fillchar(v,sizeof(v),false);111     fillchar(f,sizeof(f),false);112     fillchar(st,sizeof(st),0);113     fillchar(be,sizeof(be),0);114     sum:=0;115     for i:=1 to 2*n do116       if not v[i] then117       begin118         h:=0;119         t:=0;120         tarjan(i);121       end;122 123     flag:=true;124     for i:=1 to n do125       if be[i]=be[i+n] then126       begin127         flag:=false;128         break;129       end;130 131     if flag then writeln('GOOD') else writeln('BAD');132     dec(tot);133   end;134 end.