https://codeforces.me/contest/1971/submission/268388372
This submission was getting TLE. Basically I was constructing the implication graph from the 2-SAT clauses
Then, for each variable x, I run a DFS starting at x looking for “not x”. If there is no path, we move onto the next variable since a contradiction exists if and only if a path exists from x to not x and not x to x.
If there is a path from x to not x, I reset my “visited” vector and do the DFS from not x to x.
However, if I do not reset the visited vector when I move on to the next variable, the solution is accepted:
https://codeforces.me/contest/1971/submission/268389153
Why? If there are still nodes marked as visited shouldn’t the DFS on the next variable be invalid and eventually lead to a wrong answer? Are the tests simply insufficient?
I haven’r gone through the process of actually doing it but it seems like someone could adversarially design a graph/test case that would break this code.
Would appreciate any insight.
