算法导论 CLRS 22.1-6 解答

it2022-05-09  36

从候选点中任意选择两个点u, v:

  1. 如果存在u->v, 则u不可能为通用的汇

  2. 如果不存在则v不可能是通用的汇

 

每次选择都会去掉一个候选点,故需要选择V次, 可以使用链表来维护候选点,初始化需要O(V), 每次选择前两个即可,每次选择以及删除候选点都可以在O(1)内完成; 

由于是邻接矩阵,可以在O(1)时间判断是否存在u->v; 总的时间为O(V)

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


最新回复(0)