Graph Theory37 sections · 1633 units
Open in Course

Quiz: Debugging 2-SAT

Knowledge check

Check Your Understanding

Your 22-SAT solution reports "unsatisfiable" but you believe a solution exists. You have nn variables and check scc[i] != scc[i + n] for each variable ii. What is the most likely bug?

  1. A.Forgetting to run Tarjan's algorithm
  2. B.Not sorting the SCC numbers
  3. C.Running BFS instead of DFS for SCC
  4. D.Using i+1i + 1 instead of i+ni + n for the negation node, causing wrong variable-negation pairing
Start the roadmap to answer the quizzes and solve the challenges