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’.
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.
Graphs like
n=4
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)
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’ ) ?”
Though let me know if you can solve it using dfs.
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.
