给定有向非循环图（DAG），是否存在一个在 linear time 中运行的算法，该算法计算每个顶点（以及该边缘的源）的入度，假定我们知道一个根节点（从中可以得到一个节点）到达每个其他顶点）？
假设您的节点从1到n编号 . 有一个简单的解决方案：创建一个大小为n的数组D，其值初始化为0.然后遍历所有边（v，w）并将D [w]递增1 . 最后，D [w]将是顶点w的入度 .
1 回答
假设您的节点从1到n编号 . 有一个简单的解决方案：创建一个大小为n的数组D，其值初始化为0.然后遍历所有边（v，w）并将D [w]递增1 . 最后，D [w]将是顶点w的入度 .