※ 引述《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)的时间 有什么技巧嘛？