SPOJ.com - Problem PARADOX

https://www.spoj.com/problems/PARADOX/.

I am stuck on this spoj problem. I am not able to figure out how to convert this question in to graph data (adjacency list)?
Thanks in advance

this is standard 2-sat problem. You are supposed to make graph containing 2 vertices for the truth of each statement(eg-1 and~1) then check if they belong to same connected component or not. because if they do then its impossible.else possible.
refer-https://www.quora.com/What-is-the-algorithmic-approach-to-solving-the-problem-Paradox-on-SPOJ
https://cp-algorithms.com/graph/2SAT.html

1 Like

*strongly connected component i meant to say.
check this video to be completely clear

also you might want to study Kosaraju’s algorithm first.
Goodluck Gilfoyle!

Thanks karthikay. That video was very helpful.