3718 . [模板題] 2 Sat
TopCoder
Tags
Description
Given 2-Sat with $N$ variables and $M$ clauses. Check the satisfiability and if satisfiable, construct the assignment of variables.
Input Format
2-Sat is given as DIMACS format. Please see the samples.
p cnf $N$ $M$
$a_ 1$ $b_ 1$ 0
$a_ 2$ $b_ 2$ 0
:
$a_ M$ $b_ M$ 0
Output Format
If the input is satisfiable, print as follows:
s SATISFIABLE
v $x_ 1$ $x_ 2$ ... $x_ N$ 0
If $i$-th variable is true, $x_ i = i$, and is false, $x_ i = -i$.
If the input is not satisfiable,print as follows:
s UNSATISFIABLE
Sample Input 1
p cnf 5 6 1 2 0 -3 -1 0 -4 -3 0 2 -5 0 5 -2 0 1 4 0
Sample Output 1
s SATISFIABLE v -1 2 -3 4 5 0
Sample Input 2
p cnf 2 4 1 2 0 1 -2 0 -1 2 0 -1 -2 0
Sample Output 2
s UNSATISFIABLE
Hints
- $1 \leq N \leq 500,000$
- $1 \leq M \leq 500,000$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|