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.