Description
Katu Puzzle is presented as a directed graph G ( V , E ) with each edge e ( a , b ) labeled by a boolean operator op (oneofAND,OR,XOR) and an integer c ( 0 ≤ c ≤ 1 ) . One Katu is solvable if one can find each vertex Vi a value X i ( 0 ≤ X i ≤ 1 ) such that for each edge e(a, b) labeled by op and c, the following formula holds:
Xa op Xb = c
The calculating rules are:
AND 0 1
0 0 0
1 0 1
OR 0 1
0 0 1
1 1 1
XOR 0 1
0 0 1
1 1 0
Given a Katu Puzzle, your task is to determine whether it is solvable.
Input
The first line contains two integers N ( 1 ≤ N ≤ 1000 )and M,( 0 ≤ M ≤ 1 , 000 , 000 ) (0 ≤ M ≤ 1,000,000) indicating the number of vertices and edges.
The following M lines contain three integers a ( 0 ≤ a < N ) , b ( 0 ≤ b < N ), c and an operator op each, describing the edges.
Output
Output a line containing “YES” or “NO”.
Sample Input
4 4 0 1 1 AND 1 2 1 OR 3 2 0 AND 3 0 0 XOR
Sample Output
YES
Hint
X0 = 1, X1 = 1, X2 = 0, X3 = 1.
int n, m; struct node { int to,nex; } e[maxm << 2]; int cnt = 0, head[maxn << 1]; bool inStk[maxn << 1]; int low[maxn << 1], dfn[maxn << 1],dfc, pos[maxn << 1]; void init() { dfc = cnt = 0; for(int i=0; i <=2* n; i++) { head[i] = -1; low[i] = dfn[i] = 0; } } stack<int> stk; void add(int u,int v) { e[cnt].to = v; e[cnt].nex = head[u]; head[u] = cnt ++; } int cntSCC; void Tarjan(int u) { // cout << u << endl; dfn[u] = low[u] = ++ dfc; inStk[u] = 1; stk.push(u); for(int i=head[u]; ~i; i=e[i].nex) { itn to = e[i].to; if(!dfn[to]) { Tarjan(to); low[u] = min(low[u],low[to]); } else if(inStk[to] && !pos[to]) { low[u] = min(low[u],dfn[to]); } } if(low[u] == dfn[u]) { int tp; ++ cntSCC; do { tp = stk.top(); stk.pop(); inStk[tp] = 0; pos[tp] = cntSCC; } while(tp != u); } } int a,b,c; string op; int main() { n=read,m=read; init(); for(int i=1; i<=m; i++) { a = read,b = read,c = read; cin >> op; int u=a * 2,u1=2 * a+1; int v=b * 2,v1=2 * b+1; if(op == "AND") { if(c == 1) {/// u,v add(u1,u); add(v1,v); } else { // add(u,u1); add(u,v1); // add(v,u1); add(v,u1); } } else if(op == "OR") { if(c == 1) { // add(u1,u); add(u1,v); // add(v1,v); add(v1,u); } else { add(u,u1); add(v,v1); } } else if(op == "XOR") { if(c == 1) { add(u,v1); add(v,u1); add(u1,v); add(v1,u); } else { add(u,v); add(v,u); add(u1,v1); add(v1,u1); } } } for(int i=0; i <= 2*n; i++) { if(!dfn[i]) Tarjan(i); } for(int i=0; i <= 2*n; i++) { if(pos[i] == pos[i+1]) { puts("NO"); return 0; } i ++; } puts("YES"); return 0; }
