→ DJWS:光是讀取演算法的輸入G就要O(V+E)了 題目敘述不夠嚴謹吧... 07/31 22:52
推 fenzhang:輸入是分開算的吧，也許圖上每次增加一點就要詢問一次 08/02 02:33
我在研究所考題裡面看到這個問題。
http://rapid.lib.ncu.edu.tw:8080/cexamn/exam/EC02_102_01.pdf
內的第五題
給定一個無向連通圖，此圖必存在至少一non-cut點，使得移除此點之後圖仍然連通。
設計一演算法在O(|V|)的時間內找出non-cut點。
設計一演算法在O(|V|)的時間內找出一邊，使得移除此邊之後圖仍然連通，
或是報告此種邊不存在。
如果時間複雜度是O(|V| + |E|)，那這問題很容易解決。
如果可使用的時間只有O(|V|)，那連DFS也做不了。
我的想法是在O(|V|)時間內找到迴圈，然後在迴圈上找出non-cut點，
不過也沒成功，有沒有人有其他想法？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.170.195.151