The problem:
An undirected graph is unicyclic if it contains exactly one cycle. Describe an O( |V| + |E| ) algorithm for determining whether or not a given graph, G is unicyclic.
My solution:
int i = 0
Run a modified DFS on G, where we increment i everytime we decide not to visit a vertex because it has already been visited.
After DFS is done, if i==1, graph is unicyclic.
I thought this solution would work but am wondering if there is a counter example that would prove it false. If anyone could clarify that would be great, Thanks.
Does your graph consists of a single connected component?
In this case just count vertices and edges and check |V| - |E| = 0
Otherwise count the number of connected components O(|V| + |E|), and check |V| - |E| = number of connected components - 1.
Remark: having more than one connected component is a counterexample to your algorithm.