Graph Theory37 sections · 1633 units
Open in Course

Common Mistakes

(Avoiding pitfalls)

Mistake 11: forgetting to add both edges for each clause. The clause "a OR b" needs NOT a → b AND NOT b → a. Both edges are needed. Mistake 22: confusing node indices. Keep track of which nodes represent x and which represent NOT x.

Use a clear indexing scheme like 2i2i for xix_i and 2i+12i+1 for NOT xix_i. Be consistent. Mistake 33: using wrong SCC comparison. If SCC(x) > SCC(NOT x), set x to true. Make sure you understand your SCC algorithm's ordering convention.