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:
|
|
|
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
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <string> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 10 using namespace std; 11 const int maxn = 1e5 + 10; 12 const int mod = 1e9 + 7 ; 13 const int INF = 0x7ffffff; 14 struct node { 15 int v, next; 16 } edge[maxn]; 17 int head[maxn], dfn[maxn], low[maxn]; 18 int s[maxn], belong[maxn], instack[maxn]; 19 int tot, cnt, top, flag, n, m; 20 void init() { 21 tot = cnt = top = flag = 0; 22 memset(s, 0, sizeof(s)); 23 memset(head, -1, sizeof(head)); 24 memset(dfn, 0, sizeof(dfn)); 25 memset(instack, 0, sizeof(instack)); 26 } 27 void add(int u, int v ) { 28 edge[tot].v = v; 29 edge[tot].next = head[u]; 30 head[u] = tot++; 31 } 32 void tarjan(int v) { 33 dfn[v] = low[v] = ++flag; 34 instack[v] = 1; 35 s[top++] = v; 36 for (int i = head[v] ; ~i ; i = edge[i].next ) { 37 int j = edge[i].v; 38 if (!dfn[j]) { 39 tarjan(j); 40 low[v] = min(low[v], low[j]); 41 } else if (instack[j]) low[v] = min(low[v], dfn[j]); 42 } 43 if (dfn[v] == low[v]) { 44 cnt++; 45 int t; 46 do { 47 t = s[--top]; 48 instack[t] = 0; 49 belong[t] = cnt; 50 } while(t != v) ; 51 } 52 } 53 int check() { 54 for (int i = 0 ; i < n ; i++) 55 if (belong[2 * i] == belong[2 * i + 1]) return 0; 56 return 1; 57 } 58 int main() { 59 while(scanf("%d%d", &n, &m) != EOF) { 60 if (n == 0 && m == 0) break; 61 init(); 62 char op[10]; 63 int x, y, c; 64 for (int i = 0 ; i < m ; i++) { 65 scanf("%d%d%d%s", &x, &y, &c, op); 66 if (op[0] == ‘A‘) { 67 if (c) { 68 add(2 * x + 1, 2 * x); 69 add(2 * y + 1, 2 * y); 70 } else { 71 add(2 * x, 2 * y + 1); 72 add(2 * y, 2 * x + 1); 73 } 74 } 75 if (op[0] == ‘O‘) { 76 if (c) { 77 add(2 * x + 1, 2 * y); 78 add(2 * y + 1, 2 * x); 79 } else { 80 add(2 * x, 2 * x + 1); 81 add(2 * y, 2 * y + 1); 82 } 83 } 84 if (op[0] == ‘X‘) { 85 if (c) { 86 add(2 * x, 2 * y + 1); 87 add(2 * x + 1, 2 * y); 88 add(2 * y, 2 * x + 1); 89 add(2 * y + 1, 2 * x); 90 } else { 91 add(2 * x + 1, 2 * y + 1); 92 add(2 * x, 2 * y); 93 add(2 * y + 1, 2 * x + 1); 94 add(2 * y, 2 * x); 95 } 96 } 97 98 } 99 for (int i = 0 ; i < 2 * n ; i++) 100 if (!dfn[i]) tarjan(i); 101 if (check()) printf("YES\n"); 102 else printf("NO\n"); 103 } 104 return 0; 105 }
poj 3678 Katu Puzzle 2-SAT 建图入门
原文：https://www.cnblogs.com/qldabiaoge/p/9094609.html