作者Leon (Achilles)
站內Prob_Solve
標題Re: [問題] 在O(|V|)的時間內找到non-cut點
時間Wed Jul 31 01:49:38 2013
※ 引述《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
1F：推 seanwu:non-cut point可以不是leaf，例如完全圖上任何一點都是 07/31 02:03
2F：→ Leon:that's correct, however, my algo just want to find one 07/31 02:09
3F：推 seanwu:噢! 我誤會了你的意思了，你是指spanning tree嗎? 07/31 02:10
4F：→ Leon:其實, non-cut point is a leaf in one spanning tree 07/31 02:10
5F：→ Leon:看來你了解了, good 07/31 02:11
6F：→ seanwu:哈... 因為你第三行突然冒出"a tree"，一時沒轉過來XD 07/31 02:15
7F：→ seanwu:不過我覺得step 2.應該不是O(K)? 最差可以到 O(K^2) 吧? 07/31 02:16
8F：→ seanwu:如果是需要看過這些edge，把他們挑出來的話 07/31 02:17
9F：→ Leon:這就是巧妙的地方, 你去試一個圖做看看就知道 07/31 03:23
10F：推 FRAXIS:我也覺得在第二步的時候會需要O(k^2)的時間 有什麼技巧嘛？ 07/31 04:23