算法设计题（要求同上）：设有向图G=(V, E)以邻接表存储，V(G)={1,2,…,n}，设计算法计算G中所有顶点的入度，其结果存放在一维数组D中。

算法设计题：计算有向图 G=(V, E) 中所有顶点的入度

（1）基本思想：
对于有向图 G，入度是指指向某个顶点的边的数量。因为图是以邻接表的形式存储，所以可以直接遍历每个顶点的邻接列表，统计进入该顶点的边的数量。我们将结果存储在一个长度为 n 的一维数组 D 中，其中 D[i] 表示顶点 i 的入度。

（2）算法步骤：

def computeInDegree(graph, n):
    # 初始化入度数组 D
    degree = [0] * n

    # 遍历每个顶点及其邻接列表
    for i in range(n):
        for neighbor in graph[i]:  # 邻接表中存储的是下一个顶点
            degree[neighbor - 1] += 1  # 计算并增加进入顶点 i 的边的数量

    return degree

graph = []  # 以邻接表形式存储的有向图，如 [{1}, [2], [], ..., [n-1]]
n = len(graph)  # 图中顶点的数量
in_degrees = computeInDegree(graph, n)

关键步骤注释：
- 对于每个顶点 i，我们迭代其邻接列表（即图[i]），将每个邻接顶点的值加 1 到相应的入度位置（index为 neighbor - 1，因为邻接列表索引通常是从 0 开始的）。

（3）时间复杂度：O(V + E)，因为我们需要遍历每个顶点和它的邻接列表，总共访问 V 个顶点和 E 条边。
空间复杂度：O(V)，因为我们创建了一个大小为 n 的数组 D 来存储入度信息。