【POJ】3678 Katu Puzzle

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N=1000*2+10, M=N*N*4;
struct E { int next, to; }e[M];
int ihead[N], cnt, tot, num, vis[N], FF[N], LL[N], p[N], n, m, top, s[N];
void add(int u, int v) { e[++cnt]=(E){ihead[u], v}; ihead[u]=cnt; }
void tarjan(int x) {
	FF[x]=LL[x]=++tot; vis[x]=1; s[++top]=x;
	for(int i=ihead[x]; i; i=e[i].next) {
		if(!FF[e[i].to]) tarjan(e[i].to), LL[x]=min(LL[x], LL[e[i].to]);
		else if(vis[e[i].to]) LL[x]=min(LL[x], FF[e[i].to]);
	}
	if(FF[x]==LL[x]) {
		int y;
		++num;
		do {
			y=s[top--];
			vis[y]=0;
			p[y]=num;
		} while(x!=y);
	}
}
void clr() {
	cnt=tot=num=top=0;
	int nn=n<<1;
	memset(ihead, 0, sizeof(int)*(nn));
	memset(p, 0, sizeof(int)*(nn));
	memset(FF, 0, sizeof(int)*(nn));
}
bool check() {
	int nn=n<<1, flag=1;
	for(int i=0; i<nn; ++i) if(!FF[i]) tarjan(i);
	for(int i=0; i<nn; i+=2) if(p[i]==p[i|1]) { flag=0; break; }
	clr();
	return flag;
}
int main() {
	while(~scanf("%d%d", &n, &m)) {
		for(int i=0; i<m; ++i) {
			int a, b, c; static char s[5];
			scanf("%d%d%d%s", &a, &b, &c, s);
			a<<=1; b<<=1;
			if(s[0]==‘A‘) {
				if(c) add(a^1, a), add(b^1, b);
				else add(a, b^1), add(b, a^1);
			}
			else if(s[0]==‘O‘) {
				if(c) add(a^1, b), add(b^1, a);
				else add(a, a^1), add(b, b^1);
			}
			else {
				if(c) add(a^1, b), add(b^1, a), add(a, b^1), add(b, a^1);
				else add(a, b), add(a^1, b^1), add(b, a), add(b^1, a^1);
			}
		}
		check()?puts("YES"):puts("NO");
	}
	return 0;
}