Question

Design an algorithm that for a given DAG G = (V, E) checks/recognizes if G is semi-connected in time O(|V | + |E|). A directed graph G = (V, E) is called semi-connected if and only if for every two vertices u, v ∈ V there is a directed path from u to v or from v to u

Answer 1

A DAG is semi connected in a topological sort, for each i, there is an edge (vi,vi+1)

Complexity of Algorithm: O(|v|+|e|)

Given a DAG with topological sort v1,v2,...,vn:

If there is no edge (vi,vi+1) for some i, then there is also no path (vi+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:

1. Find Maximal SCCs in the graph
2. Build the SCC graph G'=(U,E') such that 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)
3. Do topological sort on G'
4. If there exists more than one topological order of graph G , then graph is not semi connected. Otherwise the graph is connected.

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.