AbstractIn a randomn‐vertex digraph, each arc is present with probabilityp, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, whennis large andnpis equal to a constantcgreater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about Θ2nvertices, where Θ is the unique root in [0, 1] of the equation 1 −x−e−ex= 0. Nearly all the vertices outside the large strong component line in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected timeO(n).for all choices ofnandp, the expected execution time of the algorithm isO(w(n)(nlogn)4/3), wherew(n)is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be Ω(n2)the algorithm presents the transitive closure in the compact form(A × B)UC, whereAandBare sets of vertices, andCis a