Switchboard Two-SAT Problem

Switchboard Two-SAT Problem — ExecCode Hard DSA Practice

Solve the Switchboard Two-SAT problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Each switch is true or false. Clauses are 1-based literals (negative = NOT). After Tarjan SCCs on the implication graph, you assign a variable true when its component is later in reverse topological order than its negation. If any variable shares a component with its negation, there is no assignment. Return any satisfying 0/1 list of length n, or an empty list if unsatisfiable. 1 means true. You are given: n — variables clauses — [a, b] disjunctions Return assignment or empty list. Any valid assignment is accepted by the judge; tests compare against a solver that picks the lexicographically smallest mask.

Examples

Input {'n': 1, 'clauses': [[1, 1]]}; Output [1]. Input {'n': 1, 'clauses': [[1, 1], [-1, -1]]}; Output []. Input {'n': 2, 'clauses': []}; Output [0, 0]

Constraints

Empty clauses → all-false is fine Unsatisfiable → []

Practice Switchboard Two-SAT free on ExecCode. Browse DSA problems, topic map, and placement guides.