设 n 个顶点、e 条边的有向图用邻接表表示，则求某顶点 v 的入度的时间复杂度为（　　）。

A. O(n) B. O(e) C. O(n+e) D. O(ne)

[tag_link]

正确答案：C

结论

选 C，时间复杂度为 O(n+e)。

推导

邻接表的每条边通常按出边挂在起点链表中。求顶点 v 的入度时，必须检查所有顶点的边表，判断每条边是否指向 v；因此需要遍历顶点表和边表，总复杂度为 O(n+e)。

易错点

不要把“求出度”与“求入度”混淆：出度只需扫描 v 的链表，入度没有逆邻接表时必须扫全表。