[POJ3678] Katu Puzzle | 2-SAT 入门-阿里云开发者社区

[POJ3678] Katu Puzzle | 2-SAT 入门

2022-06-14 132

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： DescriptionKatu 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 )

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;
}