卡图难题

有N个变量X0~XN−1，每个变量的可能取值为0或1。
给定M个算式，每个算式形如 XaopXb=c，其中 a,b 是变量编号，c 是数字0或1，op 是 and，or，xor 三个位运算之一。
求是否存在对每个变量的合法赋值，使所有算式都成立。

输入格式
第一行包含两个整数N和M。

接下来M行，每行包含三个整数a b c，以及一个位运算（AND,OR,XOR中的一个）。

输出格式
输出结果，如果存在，输出“YES”，否则输出“NO”

数据范围
1≤N≤1000,
1≤M≤106

输入样例：
4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR

输出样例：
YES

边很多，故不能拓展并查集，需要求SCC，然后相当于就是2-SAT问题。

找到每个之间的关系即可。

a为1，a+n为0

注意AND时，c为1，直接若有0，产生矛盾即可add(a+n,a),add(b+n,b)。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e3+10,M=1e7+10;
int n,m,vis[N];
int dfn[N],low[N],col[N],co,cnt;
int head[N],nex[M],to[M],tot;
stack<int> st;
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
void tarjan(int x){
	dfn[x]=low[x]=++cnt; vis[x]=1; st.push(x);
	for(int i=head[x];i;i=nex[i]){
		if(!dfn[to[i]]){
			tarjan(to[i]); low[x]=min(low[x],low[to[i]]);
		}else if(vis[to[i]]) low[x]=min(low[x],dfn[to[i]]);
	}
	if(dfn[x]==low[x]){
		int u; co++;
		do{
			u=st.top(); st.pop(); vis[u]=0; col[u]=co;
		}while(u!=x);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1,a,b,c;i<=m;i++){
		char op[5]; scanf("%d %d %d %s",&a,&b,&c,op); ++a,++b;
		if(op[0]=='A'){
			if(c)	add(a+n,a),add(b+n,b);
			else	add(a,b+n),add(b,a+n);
		}else if(op[0]=='O'){
			if(c)	add(a+n,b),add(b+n,a);
			else	add(a,a+n),add(b,b+n);
		}else{
			if(c)	add(a,b+n),add(b,a+n),add(a+n,b),add(b+n,a);
			else	add(a+n,b+n),add(a,b),add(b,a),add(b+n,a+n);
		}
	}
	for(int i=1;i<=(n<<1);i++)	if(!dfn[i])	tarjan(i);
	for(int i=1;i<=n;i++)	if(col[i]==col[i+n])	return puts("NO"),0;
	puts("YES");
	return 0;
}