ANSWER: D O( n3 )
Transitive closure of a graph
Given a directed graph, find out if a vertex j is reachable from another vertex I for all vertex pairs (i, j) in the given graph. Here reachable means that there is a path from vertex I to j. The reach-ability matrix is called transitive closure of a graph.
Transitive closure of above graphs is
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 1
Floyd Warshall Algorithm can be used, we can calculate the distance matrix dist[V][V] using Floyd Warshall, if dist[i][j] is infinite, then j is not reachable from i, otherwise j is reachable and value of dist[i][j] will be less than V.
Time Complexity: O(V3) where V is the number of vertices in the given graph.
source: geeksforgeeks