What is the most efficient way to determine if a directed graph is singly connected?

Question

I am working on an assignment where one of the problems asks to derive an algorithm to check if a directed graph G=(V,E) is singly connected (there is at most one simple path from u to v for all distinct vertices u,v of V.

Of course you can brute force check it, which is what I'm doing right now, but I want to know if there's a more efficient way. Could anyone point me in the right direction?

Answer 1

There is a better answer for this question. you can do that in O(|V|^2). and with more effort you can do it in linear time.

First you find strongly connected components of G. in each strong component, you search to find this cases: 1) if there is a forward edge in this component, it is not singly connected, 2) if there is a cross edge in this component, it is not singly connected, 3) if there are at least two back edges in tree rooted at vertex u, to proper ancestors of u, then it is not singly connected.

this can be done in O(E). ( I think except for case 3. I couldn't implement it well!! ).

If none of cases above occurred, you should check whether there is a cross edge or a forward edge on G^SCC ( graph G, with strong components replaced with single nodes), since we don't have backedges, it can be done by repeating dfs on each vertex of this graph in O(|V|^2).