A directed graph G = (V, E) is said to be semi-connected if, for all pairs of vertices u, v in V we have u -> v or v-> u path. Give an efficient algorithm to determine whether or not G is semi-connected
Trivial O(V^3) solution could be to use floyd warshal all-to-all shortest path, but that's an overkill (in terms of time complexity).
It can be done in O(V+E).
Claim:
A DAG is semi connected in a topological sort, for each i, there there is an edge (vi,vi+1)
Proof:
Given a DAG with topological sort v1,v2,...,vn:
If there is no edge (vi,v(i+1)) for some i, then there is also no path (v(i+1),vi) (because it's a topological sort of a DAG), and the graph is not semi connected.
If for every i there is an edge (vi,vi+1), then for each i,j (i < j) there is a path vi->vi+1->...->vj-1->vj, and the graph is semi connected.
From this we can get the algorithm:
U is a set of SCCs. E'= { (V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E }.Correctness proof:
If the graph is semi connected, for a pair (v1,v2), such that there is a path v1->...->v2 - Let V1, V2 be their SCCs. There is a path from V1 to V2, and thus also from v1 to v2, since all nodes in V1 and V2 are strongly connected.
If the algorithm yielded true, then for any two given nodes v1, v2 - we know they are in SCC V1 and V2. There is a path from V1 to V2 (without loss of generality), and thus also from v1 to v2.
As a side note, also every semi-connected graph has a root (vertex r that leads to all vertices):
Proof:
Assume there is no root. Define #(v) = |{u | there is a path from v to u}| (number of nodes that has a path from v to them).
Choose a such that #(a) = max{#(v) | for all v}.
a is not a root, so there is some node u that has no path from a to it. Since graph is semi connected, it means there is a path u->...->a. But that means #(u) >= #(a) + 1 (all nodes reachable from a and also u).
Contradiction to maximality of #(a), thus there is a root.