※ 引述《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.

non-cut point可以不是leaf，例如完全圖上任何一點都是

that's correct, however, my algo just want to find one

噢! 我誤會了你的意思了，你是指spanning tree嗎?

其實, non-cut point is a leaf in one spanning tree看來你了解了, good

哈... 因為你第三行突然冒出"a tree"，一時沒轉過來XD不過我覺得step 2.應該不是O(K)? 最差可以到 O(K^2) 吧?如果是需要看過這些edge，把他們挑出來的話

這就是巧妙的地方, 你去試一個圖做看看就知道

我也覺得在第二步的時候會需要O(k^2)的時間 有什麼技巧嘛？