C++博客-WHUGCChttp://www.cppblog.com/WHUGCC/zh-cnTue, 21 Apr 2026 20:00:11 GMTTue, 21 Apr 2026 20:00:11 GMT60URAL JUDGE ID 57735TChttp://www.cppblog.com/WHUGCC/archive/2007/09/22/32660.htmlWHUGCCWHUGCCSat, 22 Sep 2007 04:06:00 GMThttp://www.cppblog.com/WHUGCC/archive/2007/09/22/32660.htmlhttp://www.cppblog.com/WHUGCC/comments/32660.htmlhttp://www.cppblog.com/WHUGCC/archive/2007/09/22/32660.html#Feedback0http://www.cppblog.com/WHUGCC/comments/commentRss/32660.htmlhttp://www.cppblog.com/WHUGCC/services/trackbacks/32660.html

WHUGCC 2007-09-22 12:06 发表评论
]]>给出一个没有偶圈的简单无向图，求两个顶点间路径的数目。http://www.cppblog.com/WHUGCC/archive/2007/09/17/32371.htmlWHUGCCWHUGCCMon, 17 Sep 2007 13:06:00 GMThttp://www.cppblog.com/WHUGCC/archive/2007/09/17/32371.htmlhttp://www.cppblog.com/WHUGCC/comments/32371.htmlhttp://www.cppblog.com/WHUGCC/archive/2007/09/17/32371.html#Feedback0http://www.cppblog.com/WHUGCC/comments/commentRss/32371.htmlhttp://www.cppblog.com/WHUGCC/services/trackbacks/32371.html
老实说，这个题目其实不容易，在正式竞赛中肯定不属于送分题。题目的难点在于发现“没有偶圈”这个条件反映的图的特殊性质。

如提示中所说，考虑图的双连通分量。首先解释一下什么是双连通分量。无向图中某个顶点如果被删除之后，连通分量的数目增加，那么这个顶点就叫做割点。无向图中不包含割点的极大子图就是双连通分量。

双连通分量中任意两顶点共圈。从这个性质出发，可以证明：没有偶圈的简单无向图的所有双连通分量只能是2阶完全图或奇圈，收缩所有双连通分量之后得到的图是树。这两个性质意味着，图中两个顶点间的路径经过的双连通分量的序列是相同的。由此得到一下算法：

1.求出图的所有双连通分量；
2.确定从顶点u到顶点v的一条路径；
3.确定路径经过的双连通分量的序列；
4.确定序列中是奇圈的双连通分量的数目，记为k，则路径数为2^k。

在分析上述算法的复杂度之间，先补充一下图的另一个性质。因为图中没有偶圈，所以图中不包含同胚于5阶完全图或3,3完全二部图的子图，根据Kuratowski定理，这个图是平面图，由此可得m = O(n)。

现在来分析算法的复杂度。第1步可以利用J. Hopcroft提出的线性时间算法在O(n + m) = O(n)时间内完成。第2步可以用宽度优先搜索在O(n)时间内实现。第3步可以直接在O(n)时间内实现。第4步是整个算法的瓶颈。 它需要计算一个O(2^(n/2))的数值。使用一般的算法实现时间复杂度将为O(n^2)，如果使用快速正交变换实现时间复杂度将为O(nlogn)。综合以上四个结果，算法的时间复杂度是O(nlogn)。算法的空间复杂度为O(n)。

WHUGCC 2007-09-17 21:06 发表评论
]]>http://acm.hit.edu.cn/ojs/show.php?Proid=2543&Contestid=0http://www.cppblog.com/WHUGCC/archive/2007/09/17/32359.htmlWHUGCCWHUGCCMon, 17 Sep 2007 10:07:00 GMThttp://www.cppblog.com/WHUGCC/archive/2007/09/17/32359.htmlhttp://www.cppblog.com/WHUGCC/comments/32359.htmlhttp://www.cppblog.com/WHUGCC/archive/2007/09/17/32359.html#Feedback1http://www.cppblog.com/WHUGCC/comments/commentRss/32359.htmlhttp://www.cppblog.com/WHUGCC/services/trackbacks/32359.html一个最小费用，最大流，待解决。



WHUGCC 2007-09-17 18:07 发表评论
]]>