→ DJWS:光是读取算法的输入G就要O(V+E)了 题目叙述不够严谨吧... 07/31 22:52
推 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)