Here is the link to the solution and here is the problem
Can someone please explain how the solution avoided setting a “visited” flag for every node during every recursion? I don’t quite understand the editorial.
Thanks in advance!
Here is the link to the solution and here is the problem
Can someone please explain how the solution avoided setting a “visited” flag for every node during every recursion? I don’t quite understand the editorial.
Thanks in advance!
They did, it’s implicitly stored in a “map<int, Graph> regid”, if it has a regid then it’s been visited, otherwise, not.
The solution uses somewhat abstract code, in order to reuse the graph/DFS code for both stages of the problem. This is nice in some ways, but unnecessarily complex (also a bit slow because of the maps).
I would read the analysis carefully and then code up a normal DFS in a way you are familiar with, instead of necessarily relying on the code. Generally I don’t read code unless there is some detail that is critical to the solution, or after I’m done coding to see an alternative.