The comment was too short.
Your correctness proof is hardly there. I also don't know what do you mean by 'comparisons' and where from you got $2|E|$. On the other hand, this is a correct algorithm given you have a connected graph. Your comment explains what to do in disconnected case, but then you could just apply it, after all, one searches for the connected components with DFS (and those two DFSes could be just one). Moreover, one can do initialization faster, the $|V|$ part of complexity should come from the fact that in the worst case you will have to visit (or at least take care in some way) all the vertices. Of course, if you have initialization done this way, you ought to mention it (as you did; besides this is not a big fault, usually you need to read the graph from some kind of input and this is where you can initialize your arrays/maps).
Finally, this is a fine attempt, you shouldn't be discouraged. There are some issues, but I would be glad if my students had enough patience and precision to work it out as you did.
As for suggestions for complexity, the best way is to express the number of operations in your algorithm depending on some global properties, like "my algorithm visits every vertex at most 42 times and every edge at most 78" or "for every edge it does at most $|V|^{567}$ operations" and so on.
As for suggestions for correctness, one usually splits the proof into two parts: "if cycle exists, then my algorithm will return true" (or "if my algorithm returns false then graph is a forest"), and "if my algorithm returns true, then cycle exists" (or "if cycle doesn't exists, my algorithm will return false"). This is not the fastest way, but it is very easy to do serious mistakes if you prove both implications at the same time.
I hope you will find my advice usefull.
Your solution looks good to me!
I have one suggestion if you consider directed graphs. Consider the graph:
A -> B -> C
D -> F
Let's say your algorithm starts arbitrarily at node B
. It will traverse the graph through B
and C
and mark them as connected components - but it won't catch A
!
A simple way to solve this problem is to allow the DFS to traverse the graph going both forwards and backwards, as though the graph was non-directed.
This is another way to solve it: Your algorithm produces sets of connected components. Let's say, as above, that the algorithm starts at B
and produces the set {B, C}
. Then, let's say that the algorithm arbitrarily selects A
as its next starting point. When it traverses the graph to B
, it should union the new set of connected components {A}
with the already-existing set {B, C}
instead of simply skipping node B
.
In general, if you encounter a node that's already part of a group of connected components during a DFS, mark the set of connected components that the node is in and then skip the node. Then, when you've finished traversing as many nodes as possible without retracing paths found by previous DFS's, union all of the marked sets and the set produced by the most recent DFS into one set of connected components and discard the unioned sets.
Best Answer
You are basically trying to find cut vertices in a connected graph. This is a common problem, eg. see See http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/