Re: [問題] 在O(|V|)的時間內找到non-cut點

[Leon (Achilles)]

※ 引述《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
推 seanwu:non-cut point可以不是leaf，例如完全圖上任何一點都是
→ Leon:that's correct, however, my algo just want to find one
推 seanwu:噢! 我誤會了你的意思了，你是指spanning tree嗎?
→ Leon:其實, non-cut point is a leaf in one spanning tree
→ Leon:看來你了解了, good
→ seanwu:哈... 因為你第三行突然冒出"a tree"，一時沒轉過來XD
→ seanwu:不過我覺得step 2.應該不是O(K)? 最差可以到 O(K^2) 吧?
→ seanwu:如果是需要看過這些edge，把他們挑出來的話
→ Leon:這就是巧妙的地方, 你去試一個圖做看看就知道
推 FRAXIS:我也覺得在第二步的時候會需要O(k^2)的時間 有什麼技巧嘛？