how could you Describe a linear time algorithm that takes a directed graph as input and 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).
1
votes
Sounds exactly like a homework question.
– Piva
Hate to say it, but O(E+V) is linear time, so if you really understand the algorithm using an adjacency list, you already have your answer.
– Ken Wayne VanderLinde
Shouldn’t the “Describe a …” part be quoted?
– Gumbo
The question title and body are contradictory. Do you want to count the number of vertices in a graph or do you want to count, for every vertex of the graph, how many vertices are reachable from that vertex, or something else entirely? Is the graph directed or undirected?
– IVlad
its a directed graph, and we need the number of vertices that can be reached from every other vertex
– user597861
1 Answers
2
votes
Check out Kosaraju's algorithm. You should be able to deduce why the running times are what they are from the algorithm.
