作者Leon (Achilles)
站内Prob_Solve
标题Re: [问题] 在O(|V|)的时间内找到non-cut点
时间Thu Aug 1 00:40:02 2013
※ 引述《c2251393 (mrgc)》之铭言：
: 这样是O(|V|)吗?
: 如果你只是把逆边砍掉的话这样还是O(|V|+|E|)啊
我分成两篇写了.
在第一篇有提到说 I don't go throught the edges in {V_1, V_{k}}.
Because I am generating a spanning tree,
so no need for circule.
: 因为你只是把遍历的的时间 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
Yes, and now the node I have visited is {V_1, V_2, V_3, V_4}
: 然後是V_2 花2个时间
: 图变成
: 0 0 0 0
: 0 0 0 0
: 0 0 0 1
: 0 0 1 0
This is not what I mean. In this step, you have no edge needed to go
because all nodes have beend visited.
What I am thinking now, is the data structure to achieve this.
It can be represented by
visit_edge ( (j node have been visited?) && E_{i,j} )
--
一箫一剑平生意
负尽狂名十五年
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 99.70.221.70
1F：→ scwg:and exactly how are you implementing such data structure 08/01 00:59
2F：→ scwg:to achieve amortized o(|E|) ? 08/01 00:59
3F：→ scwg:Sorry, my bad, o(|E|) is too strict, the complexity that 08/01 01:02
4F：→ scwg:you need is amortized O(|V|) and how do you do that? 08/01 01:02
5F：推 rebaudiana:这样的资结感觉不存在 08/01 02:09
6F：推 ledia:如果存在的话很多问题的 order 应该可以再下修 08/01 21:31