graph - 从每个节点计算有向图中可到达节点的数量，比 O(V^2) 快吗？

Question

所以我有一个可能包含循环的有向图。对于每个节点，我需要计算从该节点可到达的节点数，并将其存储在表中。天真的方法是从每个节点使用 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)

但是，循环会破坏它。我尝试了解决方法，但似乎没有任何效果。我该怎么办？

标签： graphdynamic-programmingdepth-first-searchcycledirected-graph