PreviousNext
Coding/Graphs and trees

2-SAT forced variables

Write codeHard45 min

Your task

Given a 2-SAT instance over n boolean variables (1..n) and a list of clauses (each [a, b] meaning (a OR b), with positive i = variable i true and -i = false), first decide satisfiability. If UNSATISFIABLE, return -1. Otherwise return the count of FORCED variables: variables that take the SAME value in every satisfying assignment. Constraints: 1 <= n <= 2000; clauses may be empty, repeated, or tautological.

Examples

count_forced_variables(n: int, clauses: list[list[int]]) -> int
Example 1
Inputcount_forced_variables(3, [[1, 2], [-1, 2], [2, 3], [-3, 1]])
Output1