I gave your dfs another look, and I noticed I misunderstood the exact workings. So, forget my remarks, they are nonsense. Well done for coming up with that recursion!
But that means that my way of splitting up the recursion into manageble groups fails, for your dfs requires the full history in order to work.
So I devised a way where that history is not needed, by writing a vertex directly to the ouputpath before going into the recursion. The code is now:
and my dfs looks like:
Have tested it for the vertices 0-1, 1-0, 1-2, 2-1 and for 0-1, 1-0, 2-3, 3-2.
I am stting up a test where we have 20.000 vertices with edges i - (i + 1) for i = 0... 20.000 and a recursion depth of 1000. But that input can't be read from a txt-file, so must break into my code. I let you know!
O ja: my test for connectedness has the same order as the dfs itself, so that is not very useful, it would only double the run time.