作者c2251393 (mrgc)
看板Prob_Solve
标题Re: [问题] 在O(|V|)的时间内找到non-cut点
时间Wed Jul 31 18:02:28 2013
这样是O(|V|)吗?
如果你只是把逆边砍掉的话这样还是O(|V|+|E|)啊
因为你只是把遍历的的时间 sum(deg(v))变成 sum(deg(v))/2
所以原本sum(deg(v)) = 2|E| 而现在是sum(deg(v))/2 = |E|
现在假设有一张4阶完全图
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
从V_1开始跑 花3个时间
然後图变成了这样
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
然後是V_2 花2个时间
图变成
0 0 0 0
0 0 0 0
0 0 0 1
0 0 1 0
然後是V_3 花1个时间
图变成
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
最後是V_4 花0个时间
完成
总共花6个时间 等於图上的边数
我应该没误会Leon大的意思吧?OAO
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.42.8.155
※ 编辑: c2251393 来自: 114.42.8.155 (07/31 18:06)