作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 在O(|V|)的时间内找到non-cut点
时间Fri Aug 2 09:21:02 2013
1F：→ DJWS:光是读取演算法的输入G就要O(V+E)了 题目叙述不够严谨吧... 07/31 22:52
2F：推 fenzhang:输入是分开算的吧，也许图上每次增加一点就要询问一次 08/02 02:33
仅仅读取 vertex 的资讯
而不读取 edge 的资讯
怎麽可能判断连通？
既然一定得读取 edge
时间复杂度就至少是 O(V+E) 等级的
那麽有没有办法不必读取所有的 edge 呢？有的：
一、vertex和edge要事先处理，然後储存於一个特别的资料结构。
就好比是 binary search，除非资料预先排序，不然不可能低於线性时间。
不过题目没交代这件事，所以我们不能自行假设。
二、运用一些特别的数学性质，例如 degree = 0 or 1 的点一定是 non-cut vertex。
不过我从未听过有什麽数学性质可以在O(V)解决这问题的。
这也已经脱离演算法的范畴了，
三、randomizd algortihm。
不过不能保证100%正确，应该不是这个题目想问的方向。
我只知道这些，可能还有什麽其他的策略。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
图上每次增加一点就询问一次
那麽图上所有点和边都增加完之後
最後还是 O(V+E) 呀
也许你的意思是均摊
但是均摊不是这样用的
就好比说我要找两点之间最短路径
使用 floyd-warshall O(V^3)
图上共有 C{V,2} = O(V^2) 个点对
所以，两点之间最短路径的「均摊时间复杂度」是 O(V)
但是这并不表示两点之间最短路径的「时间复杂度」是 O(V)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 36.225.133.106
※ 编辑: DJWS 来自: 36.225.133.106 (08/02 09:21)
3F：推 FRAXIS:我觉得就想像输入是一个指标 指向一个大小为|V|的阵列 08/02 10:38
4F：→ FRAXIS:阵列每个元素是一个Adjacency List.. 08/02 10:38
5F：→ FRAXIS:也就是你所提的1 我觉得这假设蛮合理的.. 08/02 10:40
6F：→ FRAXIS:但是这题 如果不是题目出错的话 应该就是要问你提的2 08/02 10:40
7F：→ FRAXIS:看有没有特殊性质.. 08/02 10:40
※ 编辑: DJWS 来自: 36.225.133.157 (08/03 10:13)
8F：→ DJWS:我往 k-connectivity k-colorable 方向去找 结果还是没斩获 08/03 20:13