討論串[問題] 在O(|V|)的時間內找到non-cut點
共 7 篇文章
內容預覽:
僅僅讀取 vertex 的資訊. 而不讀取 edge 的資訊. 怎麼可能判斷連通？. 既然一定得讀取 edge. 時間複雜度就至少是 O(V+E) 等級的. 那麼有沒有辦法不必讀取所有的 edge 呢？有的：. 一、vertex和edge要事先處理，然後儲存於一個特別的資料結構。. 就好比是 bin
(還有486個字)
內容預覽:
我的意思是你所說的第一點. 題目叫我們O(V)的時間找NON-CUT點. 沒有要我們考慮輸入時間吧. 你可以說O(V)的演算法不存在所以題目敘述錯誤. 但不能說輸入要O(V+E)就是題目不夠嚴謹. 就我舉的例子來說，沒有錯，輸入完整張圖的確是要O(V+E). 但是如果每加一個點就詢問一次而且真的有O
(還有85個字)