有向图求每个节点到可到达图中所有节点的个数

1.初始化：为每个节点初始化一个计数器，记录从该节点出发可以到达的节点数量。
2.深度优先搜索（DFS）：从每个未访问的节点开始，进行深度优先搜索。在搜索过程中，标记访问过的节点，并更新计数器。
或
广度优先搜索（BFS）：或者使用广度优先搜索，从每个未访问的节点开始，逐层扩展，标记访问过的节点，并更新计数器。
3.更新计数器：在搜索过程中，每当访问到一个新节点，就将计数器加一。
4.结果输出：最终，每个节点的计数器值即为从该节点出发可以到达的节点数量。

dfs实现

def dfs(graph, node, visited, count):
    visited[node] = True
    count[node] += 1
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited, count)

def count_reachable_nodes(graph):
    n = len(graph)
    visited = [False] * n
    count = [0] * n

    for node in range(n):
        if not visited[node]:
            dfs(graph, node, visited, count)

    return count

# 示例图
graph = {
    0: [1, 2],
    1: [2],
    2: [3],
    3: []
}

reachable_count = count_reachable_nodes(graph)
print(reachable_count)