'In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals' (cited from https://en.wikipedia.org/wiki/Conjunctive_normal_form)
In the other words, CNF is a formula of type 
, where &represents a logical "AND" (conjunction), 
represents a logical "OR" (disjunction), and vij are some boolean variables or their negations. Each statement in brackets is called a clause, and vij are called literals.
You are given a CNF containing variables x1, ..., xm and their negations. We know that each variable occurs in at most two clauses (with negation and without negation in total). Your task is to determine whether this CNF is satisfiable, that is, whether there are such values of variables where the CNF value is true. If CNF is satisfiable, then you also need to determine the values of the variables at which the CNF is true.
It is guaranteed that each variable occurs at most once in each clause.
The first line contains integers n and m (1 ≤ n, m ≤ 2·105) — the number of clauses and the number variables, correspondingly.
Next n lines contain the descriptions of each clause. The i-th line first contains first number ki (ki ≥ 1) — the number of literals in the i-th clauses. Then follow space-separated literals vij (1 ≤ |vij| ≤ m). A literal that corresponds to vij is x|vij| either with negation, if vij is negative, or without negation otherwise.
If CNF is not satisfiable, print a single line "NO" (without the quotes), otherwise print two strings: string "YES" (without the quotes), and then a string of m numbers zero or one — the values of variables in satisfying assignment in the order from x1 to xm.
2 2 2 1 -2 2 2 -1
YES 11
4 3 1 1 1 2 3 -1 -2 3 1 -3
NO
5 6 2 1 2 3 1 -2 3 4 -3 5 4 6 2 -6 -4 1 5
YES 100010
In the first sample test formula is 
. One of possible answer is x1 = TRUE, x2 = TRUE.
题目大意：给出一个布尔表达式，它是若干个子句逻辑与的结果，每个子句则是若干个单元逻辑或的结果，每个单元是某个变量或其逻辑非。每个变量最多出现两次，即它本身和它的逻辑非。每个变量在一个子句中最多出现一次。问是否存在一组变量对应的值使得给出的表达式为真。
有好几种做法，这里说一种$O\left(n\log_2n\right)$的。把子句作为点，在有同一个变量的两个子句间连边，构成无向图，问题转化为给每条边定向，使每个点至少有一条出边。按度从小到大的顺序，每个点任意选一条边作为出边就行了。具体的看代码，因为懒得打了，就贴了官方题解里给出的代码。
代码在此。
评论 (0)
