Question 22.3-13 From CLRS
A directed graph G = (V, E)G=(V,E) is singly connected if u \leadsto vu⇝v implies that GG contains at most one simple path from uu to vv for all vertices u, v \in Vu,v∈V. Give an efficient algorithm to determine whether or not a directed graph is singly connected.
There are plenty of solutions available for this question online, but everyone uses topological sort to give O(E*V) complexity. Can anyone explain why a simple dfs solution would fail ? (Do a dfs and if you reach any node that is already visited, the answer is ‘NO’ else ‘Yes’ ) ?
Also, I thought of a DSU based solution. Initially each node is a strongly connected component. Now when we add an edge between two components, we do a DSU. If we ever try to add edge between two nodes that belong to same connected component, answer is ‘NO’ else ‘YES’.
Can anyone help ??