题意：
给一堆布尔表达式，问是否存在解。
分析：
2-sat的入门题，只需判断是否有解，不要求输出解。
代码：
//poj 3678
//sep9
#include <iostream>
#include <stack>
using namespace std;
const int maxN=10024;
const int maxM=4200000;
int e,n,m,t,ecnt;
int head[maxN],ins[maxN],low[maxN],dfn[maxN];
int sol[maxN],belong[maxN];
stack<int> s;
struct Edge
{int v,next;
}edge[maxM];void addegde(int u,int v)
{edge[e].v=v;edge[e].next=head[u];head[u]=e++;
}void dfs(int x)
{low[x]=dfn[x]=++t; s.push(x);ins[x]=1;for(int i=head[x];i!=-1;i=edge[i].next){int v=edge[i].v;if(!dfn[v]){dfs(v);low[x]=min(low[x],low[v]);}else if(ins[v]==1)low[x]=min(low[x],dfn[v]);} if(dfn[x]==low[x]){++ecnt; int k;do{k=s.top();s.pop();ins[k]=0;belong[k]=ecnt;}while(dfn[k]!=low[k]);}
}
bool two_sat()
{memset(ins,0,sizeof(ins)); memset(dfn,0,sizeof(dfn)); while(!s.empty()) s.pop();int i;t=0,ecnt=0;for(i=1;i<=2*n;++i)if(!dfn[i])dfs(i);for(i=1;i<=n;++i)if(belong[i]==belong[i+n])return false;return true;
}int main()
{int a,b,c;char op[8];e=0;memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);while(m--){scanf("%d%d%d%s",&a,&b,&c,op); ++a,++b;if(op[0]=='O'){if(c==1){addegde(a+n,b);addegde(b+n,a);}else if(c==0){addegde(a,a+n);addegde(b,b+n);} }else if(op[0]=='A'){if(c==1){addegde(a+n,a);addegde(b+n,b);}else if(c==0){addegde(a,b+n);addegde(b,a+n);} }else if(op[0]=='X'){if(c==1){addegde(a,b+n);addegde(b,a+n);addegde(a+n,b);addegde(b+n,a); }else{addegde(a,b);addegde(b,a);addegde(a+n,b+n);addegde(b+n,a+n);} } }bool ans=two_sat();printf("%s",ans==true?"YES":"NO");return 0;
}