algorithm - 有向图的邻接表表示

给定有向图的邻接表表示形式，需要多长时间
计算每个顶点的出度？计算
以度为单位？
谢谢

最佳答案

两者都是O(m + n)，其中m是边数，n是顶点数。
启动一组计数器，每个顶点一个，一个用于输入度数，一个用于输出度数。
扫描边缘对于每条边的外顶点，在该顶点的外度数计数器中添加一个对于每条边的in顶点，将一个添加到该顶点的in degree计数器中。这是O(m)操作。
输出每个顶点的输出度数和输入度数计数器，即O(n)。
你就是这样得到O(m + n)。