CLRS 22.3-13

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 ??
@l_returns ?


I think you are right about DFS.
The solution should be run a DFS from every node, which apparently leads to a complexity of
O(|V|(|V| + |E|)). However, you can get O(|V| + |E|) just by not visiting previously traversed nodes twice and by starting new DFS from nodes with in-degree = 0.


I wonder if it is correct, why not it is mentioned anywhere on the internet.

1 Like

Graphs like
1 3
2 3
1 4
2 4
( Answer should be Yes but it will output No )
Will fail in DFS solution I think.
Let me know if I am missing anything.
And won’t this case fail even with DSU solution ?
Suppose you merge in following order

1 3
2 3
1 4
2 4 ( it will print No here as 1,2,3,4 all are in same DSU component)

1 Like

Why should a DFS solution answer No?

How it won’t ?
You do DFS from node 1 (visit 1,3,4) and then by node 2 ( visit 2,3,4) and hence you print No because you are visiting 3,4 twice.

To print No you should visit a node twice during the same DFS.
For example:
1 2
1 3
2 4
3 4
Because you have found 2 different paths from 1 to 4.

So will you maintain two visited arrays or will you do DFS from each node again ?

BTW I was not replying to you.
My reply was to this
“(Do a dfs and if you reach any node that is already visited, the answer is ‘NO’ else ‘Yes’ ) ?” :stuck_out_tongue:
Though let me know if you can solve it using dfs.

1 Like

Ops… alright. I should have found the problem.
Suppose to have:

1 2
2 3
4 2
4 3

Then suppose to start the first DFS from 1.
During the second DFS (from 4) you want to stop the search once reached 2 (which has been already visited). But in this way you cannot notice the multiple paths from 4 to 3.

1 Like

link , this is the right implementation of dfs, its used for checking cycles in directed graphs

1 Like