给出一个没有偶圈的简单无向图，求两个顶点间路径的数目。
老实说，这个题目其实不容易，在正式竞赛中肯定不属于送分题。题目的难点在于发现“没有偶圈”这个条件反映的图的特殊性质。
如提示中所说，考虑图的双连通分量。首先解释一下什么是双连通分量。无向图中某个顶点如果被删除之后，连通分量的数目增加，那么这个顶点就叫做割点。无向图中不包含割点的极大子图就是双连通分量。
双连通分量中任意两顶点共圈。从这个性质出发，可以证明：没有偶圈的简单无向图的所有双连通分量只能是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)。