Подсчитать количество достижимых узлов в направленном графике от каждого узла быстрее, чем O (V ^ 2)?

Итак, у меня есть ориентированный график, который может содержать циклы. Мне нужно для каждого узла подсчитать количество узлов, доступных из этого узла, и сохранить это в таблице. Наивный подход заключался бы в использовании DFS с каждого узла, что привело бы к сложности не более O (V ^ 2), что слишком медленно.

Решить эту проблему было бы легко, если бы не было циклов, используя такой алгоритм:

array numReachable(V elements of -1)

dfs(u):
    if (numReachable[u] != -1) return numReachable[u]
    mark u as VISITED
    count = 1
    for each node v adjacent to u:
        if (v is UNVISITED):
            count += dfs(v)
    mark u as UNVISITED
    return numReachable[u] = count

for each node u:
    dfs(u)

Однако циклы ломают его. Я пробовал обходные пути, но ничего не работает. Что мне делать?