Singly connected Graph?

Question

A singly connected graph is a directed graph which has at most 1 path from u to v ∀ u,v.

I have thought of the following solution:

1. Run DFS from any vertex.
2. Now run DFS again but this time starting from the vertices in order of decreasing finish time. Run this DFS only for vertices which are not visited in some previous DFS. If we find a cross edge in the same component or a forward edge, then it is not Singly connected.
3. If all vertices are finished and no such cross of forward edges, then singly connected.

O(V+E)

Is this right? Or is there a better solution.

Update : atmost 1 simple path.

Answer 1

Is this right?

No, it's not right. Considering the following graph which is not singly connected. The first component comes from a dfs beginning with vertex b and the second component comes from a dfs beginning with vertex a.

---

The right one:

Do the DFS, the graph is singly connected if all of the three following conditions satisfies:

1. no foward edges
2. no cross edges in the same component
3. there is no more than 1 cross edges between any two of components

Answer 2

A singly connected component is any directed graph belonging to the same entity. It may not necessarily be a DAG and can contain a mixture of cycles.

Every node has atleast some link(in-coming or out-going) with atleast one node for every node in the same component. All we need to do is to check whether such a link exists for the same component.

Singly Connected Component could be computed as follows:

• Convert the graph into its undirected equivalent
• Run DFS and set the common leader of each node

Run an iteration over all nodes. If all the nodes have the same common leader, the undirected version of the graph is singly connected.

Else, it contains of multiple singly connected subgraphs represented by their corresponding leaders.

Answer 3

A graph is not singly connected if one of the two following conditions satisfies:

1. In the same component, when you do the DFS, you get a road from a vertex to another vertex that has already finished it's search (when it is marked BLACK)

2. When a node points to >=2 vertices from another component, if the 2 vertices have a connection then it is not singly connected. But this would require you to keep a depth-first forest.