Linear time algorithm that takes a direct graph and returns the number of vertices

how could you Describe a linear time algorithm that takes a directed graph as input a开发者_开发百科nd returns the number of vertices that can be reached from every other vertex. i know that the algorithm would take linear time but why. and also why would it be (O(V2) on an adjacency matrix; O(E+V) on an adjacency list).

Check out Kosaraju's algorithm. You should be able to deduce why the running times are what they are from the algorithm.