Hi I was wondering if someone could help answer a question for me. I was working on a problem from my algorithms class that asks for an algorithm to determine whether or not a graph is singly connected. By singly connected it states the graph is connected i.e. there is a simple path from u-->v for all u,v in V and that there are at most one of these paths.

Oh I should mention this is a DAG.

The question is in the DFS section so I assume that want to use that the standard solution seems to be to do a DFS on every vertex and ensure that there are only forward, and tree edges in the solution this makes sense to me but I am wondering if anyone sees anything wrong with the following solution

Do a DFS on the graph the algorithm in my book stores a nodes parent when it finds it. After DFS finishes if all nodes have not been examined then we know that the graph is not connected so we can stop there.

Otherwise do a second DFS on the graph except this time do not set the parent node instead

White Nodes:

When we find a white node u ensure that u's parent is set as the current node we are looking at i.e. we discovered u from the current node in the first traversal otherwise we have 2 paths to u and we can return false.

Grey/Black Nodes:

Originally when we find an edge Grey-->Grey or Grey-->Black we essentially ignore it in the modified algorithm we would ensure that the grey node is set as grey or black nodes parent otherwise during the first traversal we discovered this node from somewhere else and there are two paths to the node return false.

The standard solution runs in V*(V+E) and mine would be 2(V+E) I can't imagine I randomly came up with an algo with marked improvement on the first instinct but I've thought about it for a while and it seems like mine would come up with the right solution.

If anyone could provide a counter example or explain why mine is wrong I greatly appreciate it.


closed as unclear what you're asking by Mike Pierce, Aloizio Macedo, Fabian, Claude Leibovici, user228113 Jan 2 '16 at 8:25

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Please add some punctuation to your question.. it's almost completely incomprehensible. $\endgroup$ – Haile Dec 2 '12 at 14:45