记录编号	571734	评测结果	AAAAA
题目名称	POJ 3678]卡图难题	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-06-16 22:04:07	内存使用	0.00 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <stack>
#define min(x,y) x < y ? x : y
using namespace std;
const int maxN = 1e3 + 10, maxM = 1e6 + 10;

void tarjan(int x);
void add(int x, int y);

int m, n;
int head[maxN], ver[maxM], Next[maxM], tot,
	C[maxN], dfn[maxN], low[maxN], cnt, num;
bool ans[maxN];
stack <int> st;
int main(void){
	freopen("katu.in", "r", stdin);
	freopen("katu.out", "w", stdout);
	scanf("%d%d", &n, &m);
	int a, b, c;
	char op[5];
	for (int i = 1; i <= m; i ++){
		scanf("%d%d%d%s", &a, &b, &c, op);
		if (op[0] == 'A'){
			if (c){
				add(a, a + n);
				add(b, b + n);
			}
			else{
				add(a + n, b);
				add(b + n, a);
			}
		}
		else if (op[0] == 'O'){
			if (c){
				add(a, b + n);
				add(b, a + n);
			}
			else{
				add(a + n, a);
				add(b + n, b);
			}
		}
		else{
			if (c){
				add(a, b + n);
				add(b, a + n);
				add(a + n, b);
				add(b + n, a);
			}
			else{
				add(a, b);
				add(b, a);
				add(a + n, b + n);
				add(b + n, a + n);
			}
		}
	}
	for (int i = 0; i <= n >> 1; i ++)
		if (!dfn[i])
			tarjan(i);
	bool flag = true;
	for (int i = 0; i < n; i ++)
		if (C[i] == C[i + n]){
			flag = false;
			break;
		}
	flag ? puts("YES") : puts("NO");
	//system("pause");
	return 0;
}

void add(int x, int y){
	ver[++ tot] = y;
	Next[tot] = head[x];
	head[x] = tot;
}

void tarjan(int x){
	dfn[x] = low[x] = ++ num;
	st.push(x);
	ans[x] = true;
	for (int i = head[x]; i; i = Next[i]){
		if (!dfn[ver[i]]){
			tarjan(ver[i]);
			low[x] = min(low[x], low[ver[i]]);
		}
		else if (ans[ver[i]])
			low[x] = min(low[x], dfn[ver[i]]);
	}
	if (dfn[x] == low[x]){
		cnt ++;
		int y;
		do{
			y = st.top();
			st.pop();
			ans[y] = false;
			C[y] = cnt;
		}while (x != y);
	}
}