作者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