O(m+n) algorithm to check if a directed graph is unilaterally connected

user_12676280 0
Viewed 2111

Given a directed graph G=(V,E) how can I check to see if it is unilaterally connected i.e. for any two pair of vertices a and b, at least one of the following condition is satisfied:

  1. There is a path from a to b.
  2. There is a path from b to a.
graph-theory graph-algorithm graph data-structures algorithm
2 Answers

Find the strongly connected components with, say, Tarjan's algorithm. Every node in an SCC is reachable from any other, so they are equivalent in terms of which nodes they can reach and be reached by. Collapse each SCC into a single vertex, and the resulting DAG will be unilateral iff the original graph was unilateral.

A DAG is unilateral iff if it is a total ordering, i.e, if there is only one topological order. If there is a path from A to B, then A must come before B. If there is a path from B to A, then B must come before A. You won't have both, because the graph is now acyclic. If there is no path between A and B, then then they are not ordered and there are at least 2 topological orders for the graph -- one with A before B, and one with B before A.

A fast way to check for a total order is to do a topological sort with Kahn's algorithm, and check to ensure that there is only one choice for the next vertex at every iteration.

Tarjan's algorithm for finding SCCs, collapsing the SCCs, and Kahn's algorithm for topological sort, all run in O(V+E) time.

user_54835260

Idea

The idea is to use SCC (Strongly Connected Component) and Top Sort . Here is a pseudo algorithm :

  • First find the SCCs of your original Graph . In each of your SCCs , there is a path from one vertex to another .
  • Compress your newly found SCC graph to a new graph . The idea is to consider all the nodes that are part of SCC 1 as your node 1 of the new graph and so on
  • Now , we need to run a DFS to check if there is only one connected component . But we can't just run DFS from any node as this is a directed graph . We use top sort to find the topological order and then run a DFS to check if there is only one component . If there is more than one , then the graph is not unilateral .

Corner Case

If initially the original graph is a forest (aka disconnected) , it is not unilateral .

Complexity

Finding SCCs takes 2 DFS . Top Sort also takes 1 DFS .
So , time complexity is O(V+E) as you wanted

I don't have any formal proof for this . But this should work . Let me know if you have any confusion .

user_107125840
Related