→ DJWS:光是讀取演算法的輸入G就要O(V+E)了 題目敘述不夠嚴謹吧... 07/31 22:52
推 fenzhang:輸入是分開算的吧，也許圖上每次增加一點就要詢問一次 08/02 02:33
僅僅讀取 vertex 的資訊
而不讀取 edge 的資訊
怎麼可能判斷連通？
既然一定得讀取 edge
時間複雜度就至少是 O(V+E) 等級的
那麼有沒有辦法不必讀取所有的 edge 呢？有的：
一、vertex和edge要事先處理，然後儲存於一個特別的資料結構。
就好比是 binary search，除非資料預先排序，不然不可能低於線性時間。
不過題目沒交代這件事，所以我們不能自行假設。
二、運用一些特別的數學性質，例如 degree = 0 or 1 的點一定是 non-cut vertex。
不過我從未聽過有什麼數學性質可以在O(V)解決這問題的。
這也已經脫離演算法的範疇了，
三、randomizd algortihm。
不過不能保證100%正確，應該不是這個題目想問的方向。
我只知道這些，可能還有什麼其他的策略。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
圖上每次增加一點就詢問一次
那麼圖上所有點和邊都增加完之後
最後還是 O(V+E) 呀
也許你的意思是均攤
但是均攤不是這樣用的
就好比說我要找兩點之間最短路徑
使用 floyd-warshall O(V^3)
圖上共有 C{V,2} = O(V^2) 個點對
所以，兩點之間最短路徑的「均攤時間複雜度」是 O(V)
但是這並不表示兩點之間最短路徑的「時間複雜度」是 O(V)