Re: [問題] 在O(|V|)的時間內找到non-cut點
看板Prob_Solve (計算數學 Problem Solving)作者c2251393 (mrgc)時間11年前 (2013/07/31 18:02)推噓0(0推 0噓 0→)留言0則, 0人參與討論串4/7 (看更多)
這樣是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)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 4 之 7 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
