Hi community!
Today I am interested in this problem:
Given a directed graph, define f(v) to be the number of nodes i such you can reach i from v by moving along edges. For which values of v is f(v) maximum?
I can come up with the O(n2) algorithm, but I wonder if there is an O(n) algorithm.
Thanks!
Are you sure? You'll count one node several times.
The science does not now any way of solving this problem faster than O(min(nm, nω)), where ω is a matrix multiplication constant (around 2.3). Could you please share your approach?