作者DJWS (...)
看板Prob_Solve
標題Re: [問題] 在O(|V|)的時間內找到non-cut點
時間Fri Aug 2 09:21:02 2013
1F：→ DJWS:光是讀取演算法的輸入G就要O(V+E)了 題目敘述不夠嚴謹吧... 07/31 22:52
2F：推 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)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.133.106
※ 編輯: DJWS 來自: 36.225.133.106 (08/02 09:21)
3F：推 FRAXIS:我覺得就想像輸入是一個指標 指向一個大小為|V|的陣列 08/02 10:38
4F：→ FRAXIS:陣列每個元素是一個Adjacency List.. 08/02 10:38
5F：→ FRAXIS:也就是你所提的1 我覺得這假設蠻合理的.. 08/02 10:40
6F：→ FRAXIS:但是這題 如果不是題目出錯的話 應該就是要問你提的2 08/02 10:40
7F：→ FRAXIS:看有沒有特殊性質.. 08/02 10:40
※ 編輯: DJWS 來自: 36.225.133.157 (08/03 10:13)
8F：→ DJWS:我往 k-connectivity k-colorable 方向去找 結果還是沒斬獲 08/03 20:13