作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 在O(|V|)的时间内找到non-cut点
时间Tue Jul 30 19:59:12 2013
我在研究所考题里面看到这个问题。
http://rapid.lib.ncu.edu.tw:8080/cexamn/exam/EC02_102_01.pdf
内的第五题
给定一个无向连通图，此图必存在至少一non-cut点，使得移除此点之後图仍然连通。
设计一演算法在O(|V|)的时间内找出non-cut点。
设计一演算法在O(|V|)的时间内找出一边，使得移除此边之後图仍然连通，
或是报告此种边不存在。
如果时间复杂度是O(|V| + |E|)，那这问题很容易解决。
如果可使用的时间只有O(|V|)，那连DFS也做不了。
我的想法是在O(|V|)时间内找到回圈，然後在回圈上找出non-cut点，
不过也没成功，有没有人有其他想法？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 129.170.195.151
1F：→ DJWS:光是读取演算法的输入G就要O(V+E)了 题目叙述不够严谨吧... 07/31 22:52
2F：推 fenzhang:输入是分开算的吧，也许图上每次增加一点就要询问一次 08/02 02:33