is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

Question

I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition):

A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ implies that $G$ contains at most one simple path from $u$ to $v$ for all vertices $u, v\in G$. Give an efficient algorithm to determine whether or not a directed graph is singly connected.

Previous threads on this question are here and here. In that second thread, one of the answers links to a preprint by someone who corresponded with one of the authors of the book, and stated (in the abstract of the preprint) that the solution the authors intended was (if I'm understanding correctly) to call DFS-VISIT(G, u) (from p. 604 of CLRS) on each vertex $u$ of the graph, resetting all vertex colors back to white (to indicate unvisited) in between calls, and return false (for "not singly connected") whenever a forward edge or cross edge is found, and returning true otherwise. This would take O(VE) time.

There seems to be some confusion in the answers and comments section of those threads: the above scheme is referred to as "calling DFS on every vertex". In fact, this is different from the DFS algorithm presented on p. 604 of CLRS, which calls DFS-VISIT on all unvisited nodes in the graph, without resetting the colors in between calls, which takes $O(V + E)$ time.

My question is, instead of doing what is stated in the preprint, which takes O(VE) time, is it sufficient to simply perform the ordinary $O(V + E)$ DFS on the graph, and return false (for "not singly connected") whenever a forward edge or a cross edge that is located entirely within a single DF tree is found? (As correctly pointed out in one of the comments in the second thread linked above, a cross edge within a single DF tree means the graph is certainly not singly connected, but a cross edge between two vertices in different trees does not necessarily mean so).

In other words, is it possible to have a non-singly connected graph, such that for some ordering of the adjacency lists, performing the DFS algorithm from p. 604 of CLRS will not find any forward edges or cross edges within individual trees, but possibly only cross edges between trees, if any?

Answer 1

I just realized, a single call to DFS is not sufficient, since the conjecture I asked about is not true. Here is a counterexample. Suppose DFS first visits all nodes in a tree rooted at $u$, and $v$ is a descendant of $u$. Then suppose an unvisited vertex $w$ has both $u$ and $v$ in its adjacency list. Then, $w$ would not be in the same tree as $u$ and $v$, but there would be cross-tree edges $(w, u)$ and $(w, v)$, and hence there would be more than two paths from $w$ to $v$, making the graph not singly connected.

However, we cannot modify the algorithm to also look for cross edges between trees, since if we removed the $(w,u)$ edge from the example above, then it's still possibly for it to be singly connected even though there's a $(w,v)$ cross edge.

Answer 2

You can check if there is already a path between u and v, using their finishing and discovery time (d[u] u is an ancestor of v). If their times are disjoint, then they are on different branches and not reachable from one another, so there shouldn't be more than one path between w and u or w and v.