Re: [問題] 在O(|V|)的時間內找到non-cut點
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/07/31 01:49)推噓3(3推 0噓 7→)留言10則, 3人參與討論串2/7 (看更多)
※ 引述《FRAXIS (喔喔)》之銘言：
: 我在研究所考題裡面看到這個問題。
: http://rapid.lib.ncu.edu.tw:8080/cexamn/exam/EC02_102_01.pdf
: 內的第五題
: 給定一個無向連通圖，此圖必存在至少一non-cut點，使得移除此點之後圖仍然連通。
: 設計一演算法在O(|V|)的時間內找出non-cut點。
: 設計一演算法在O(|V|)的時間內找出一邊，使得移除此邊之後圖仍然連通，
: 或是報告此種邊不存在。
嗯.. 其實這是 BFS 啦,
只是你需要一點技巧來分析.
Non-cut point -> leaf in a tree.
注意這個地方, 你只要找到 "一個" leaf 就行了,
而且這個圖是 uni-directional.
The rough algorithm is..
1. Start from arbitart point V_1, then find connected vertices
{V_{k}} with time |V_{k}|
2. Notice that, we don't need to consider the circule in Spanning tree.
Thus, we can igonore the edges between {V_1, V_{k} }.
3. Then pick up any node in {V_{k}}. Now the graph has size N-k.
We can write a recursive form by
T(N) = T(N-k) + K.
Q.E.D
找 edge 類似, 只是改成 circle.
--
一簫一劍平生意
負盡狂名十五年
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.170.77.110
推
07/31 02:03, , 1F
07/31 02:03, 1F
→
07/31 02:09, , 2F
07/31 02:09, 2F
推
07/31 02:10, , 3F
07/31 02:10, 3F
→
07/31 02:10, , 4F
07/31 02:10, 4F
→
07/31 02:11, , 5F
07/31 02:11, 5F
→
07/31 02:15, , 6F
07/31 02:15, 6F
→
07/31 02:16, , 7F
07/31 02:16, 7F
→
07/31 02:17, , 8F
07/31 02:17, 8F
→
07/31 03:23, , 9F
07/31 03:23, 9F
推
07/31 04:23, , 10F
07/31 04:23, 10F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
