討論串[問題] 在O(|V|)的時間內找到non-cut點
共 7 篇文章
內容預覽:
我的意思是你所說的第一點. 題目叫我們O(V)的時間找NON-CUT點. 沒有要我們考慮輸入時間吧. 你可以說O(V)的演算法不存在所以題目敘述錯誤. 但不能說輸入要O(V+E)就是題目不夠嚴謹. 就我舉的例子來說，沒有錯，輸入完整張圖的確是要O(V+E). 但是如果每加一個點就詢問一次而且真的有O
(還有85個字)
內容預覽:
僅僅讀取 vertex 的資訊. 而不讀取 edge 的資訊. 怎麼可能判斷連通？. 既然一定得讀取 edge. 時間複雜度就至少是 O(V+E) 等級的. 那麼有沒有辦法不必讀取所有的 edge 呢？有的：. 一、vertex和edge要事先處理，然後儲存於一個特別的資料結構。. 就好比是 bin
(還有486個字)
內容預覽:
我分成兩篇寫了.. 在第一篇有提到說 I don't go throught the edges in {V_1, V_{k}}.. Because I am generating a spanning tree,. so no need for circule.. Yes, and now the
(還有226個字)
內容預覽:
這樣是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
(還有213個字)
內容預覽:
技巧就是說破了不值一毛錢的小東西.. 舉個簡單的例子, 4 Node graph, as a ring.. The neighboring matrix is. 0 1 0 1 ;. 1 0 1 0 ;. 0 1 0 1 ;. 1 0 1 0 ;. So.. if you start from th
(還有384個字)