题目描述
没什么好说的
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+5,maxm=1e6+3,inf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct Graph{
int tot,head[maxn];
struct Edge{int ver,next;}edge[maxm];//边数
void add(int u,int v) {
edge[++tot].ver=v; edge[tot].next=head[u]; head[u]=tot;
}
int low[maxn],num,dfn[maxn] ;//回溯值与时间戳
int stck[maxn],ins[maxn],top;//栈
vector<int> scc[maxn]; int cnt,c[maxn];//连通分量
void tarjan(int x) {
dfn[x]=low[x]=++num;
stck[++top]=x; ins[x]=1;
for(int i=head[x],y;i;i=edge[i].next) {
if(!dfn[y=edge[i].ver]) {
tarjan(y);
low[x]=min(low[x],low[y]);
} else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]) {
cnt++; int z;
do{
z=stck[top--]; ins[z]=0;
c[z]=cnt,scc[cnt].push_back(z);
} while(x!=z);
}
}
}g;
int n,m;
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>n>>m;
while(m--) {
int a,b,c; string ch;
cin>>a>>b>>c>>ch; a++,b++;
if(ch=="AND") {
if(c==0) g.add(a,b+n),g.add(b,a+n);
else g.add(a+n,a),g.add(b+n,b);
}
if(ch=="OR") {
if(c==0) g.add(a,a+n),g.add(b,b+n);
else g.add(a+n,b),g.add(b+n,a);
}
if(ch=="XOR") {
if(c==0)
g.add(a,b),g.add(b,a),g.add(b+n,a+n),g.add(a+n,b+n);
else
g.add(a,b+n),g.add(a+n,b),g.add(b,a+n),g.add(b+n,a);
}
}
for(int i=1;i<=2*n;i++) {
if(!g.dfn[i]) g.tarjan(i);
}
for(int i=1;i<=n;i++) {
if(g.c[i]==g.c[i+n]) {
cout<<"NO\n";
return 0;
}
}
cout<<"YES\n";
return 0;
}