『算法-ACM 竞赛-图论』2-SAT-poj3678-KatuPuzzle（模板题）

图论–2-SAT–poj 3678-Katu Puzzle（模板题）

Description

Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 ≤ c ≤ 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 ≤ Xi ≤ 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) 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.

题意：给出 N 个布尔变量，每个变量要么真要么假。现在给出 M 个关系，问你是否存在一组解满足所有条件。

思路：

一：对于 AND

1，c == 1 时，则 a 和 b 全为真，建边 !a -> a 和 !b -> b；

2，c == 0 时，则 a 和 b 至少一个为假，建边 a -> !b 和 b -> !a；

二：对于 OR

1，c == 1 时，则 a 和 b 至少一个为真，建边!a -> b 和 !b -> a；

2，c == 0 时，则 a 和 b 全为假，建边 a -> !a 和 b -> !b；

三：对于 XOD

1，c == 1 时，则 a 和 b 不同，建边!a -> b 、!b -> a、a -> !b 、 b -> !a；

2，c == 0 时，则 a 和 b 相同，建边 a -> b 、b -> a、!a -> !b 、 !b -> !a；

建好图，tarjan 求 SCC 判断是否矛盾即可。