Re: [問題] 在O(|V|)的時間內找到non-cut點
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/08/01 00:40)推噓2(2推 0噓 4→)留言6則, 3人參與討論串5/7 (看更多)
※ 引述《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
→
08/01 00:59, , 1F
08/01 00:59, 1F
→
08/01 00:59, , 2F
08/01 00:59, 2F
→
08/01 01:02, , 3F
08/01 01:02, 3F
→
08/01 01:02, , 4F
08/01 01:02, 4F
推
08/01 02:09, , 5F
08/01 02:09, 5F
推
08/01 21:31, , 6F
08/01 21:31, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 7 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
