假设有n个顶点、e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度

在邻接表表示的有向图中，删除与某个点v相关的所有边的时间复杂为O(e)，其中e表示边的总数。

在邻接表中，每个顶点维护一个邻接链表，存储与该顶点相关的边。要删除与顶点v相关的所有边，需要遍历每个顶点的邻接链表，找到所有指向顶点v的边，并将其删除。由于每条边都只会在起始顶点的邻接链表中出现一次，因此需要遍历所有顶点的邻接链表，共需遍历e条边。

因此，删除与某个顶点v相关的所有边的时间复杂度为O(e)。

相关问题

10. 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示， 则表头向量大小为 （ ），邻接表的边结点个数为（ ）。

对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，表头向量大小为 n，邻接表的边结点个数为 2e。

无向图每条边都对应着两个顶点之间的关系，因此每个顶点在邻接表中都需要维护与它相邻的所有顶点，也就是说，表头向量需要有 n 个元素。而每条边都需要在邻接表中表示出来，由于每个顶点的度数等于与它相邻的边数，因此邻接表的边结点个数为 2e。

设N个顶点E条边的图用邻接表存储，则求每个顶点入度的时间复杂度为：

如果使用邻接表存储图，则可以采用统计每个顶点在所有邻接表中出现的次数的方法来计算每个顶点的入度。具体地，可以遍历邻接表中的所有边，对于每条边的终点，将其对应顶点的入度加1。由此，对于图中的每个顶点，都需要遍历其所有的邻接表，因此时间复杂度为O(E)，其中E为边的数量。

需要注意的是，在有向图中，每个顶点的出度和入度之和等于该顶点的度数，因此也可以统计每个顶点的度数来求出每个顶点的入度。但是在无向图中，每个顶点的度数等于其相邻顶点的数量，因此不能使用此方法来计算入度。