算法导论 CLRS 22.1-4 解答

it2022-05-09  39

 

使用一个额外的数组A[V], 初始化为-1, 时间为O(V); 注意只需要一次初始化就可以

遍历v的邻接表,每项a有三种情况:

  1. 如果a == v, 说明为环,删除该项

      2. A[a] != v,说明为第一条v->a的边,A[a]=v

      3. A[a] == v, 删除

总时间为O(E+V)

 

网上直接搜到的一个解答要求邻接表内部列表是增序的,这个解答没有这个限制

转载于:https://www.cnblogs.com/ellusak/archive/2012/07/27/2611189.html


最新回复(0)