[問題] 在O(|V|)的時間內找到non-cut點
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間11年前 (2013/07/30 19:59)推噓1(1推 0噓 1→)留言2則, 2人參與討論串1/7 (看更多)
我在研究所考題裡面看到這個問題。
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
→
07/31 22:52, , 1F
07/31 22:52, 1F
推
08/02 02:33, , 2F
08/02 02:33, 2F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 7 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
