給出一個沒有偶圈的簡單無向圖，求兩個頂點間路徑的數(shù)目。
老實說，這個題目其實不容易，在正式競賽中肯定不屬于送分題。題目的難點在于發(fā)現(xiàn)“沒有偶圈”這個條件反映的圖的特殊性質。
如提示中所說，考慮圖的雙連通分量。首先解釋一下什么是雙連通分量。無向圖中某個頂點如果被刪除之后，連通分量的數(shù)目增加，那么這個頂點就叫做割點。無向圖中不包含割點的極大子圖就是雙連通分量。
雙連通分量中任意兩頂點共圈。從這個性質出發(fā)，可以證明：沒有偶圈的簡單無向圖的所有雙連通分量只能是2階完全圖或奇圈，收縮所有雙連通分量之后得到的圖是樹。這兩個性質意味著，圖中兩個頂點間的路徑經過的雙連通分量的序列是相同的。由此得到一下算法：
1.求出圖的所有雙連通分量；
2.確定從頂點u到頂點v的一條路徑；
3.確定路徑經過的雙連通分量的序列；
4.確定序列中是奇圈的雙連通分量的數(shù)目，記為k，則路徑數(shù)為2^k。
在分析上述算法的復雜度之間，先補充一下圖的另一個性質。因為圖中沒有偶圈，所以圖中不包含同胚于5階完全圖或3,3完全二部圖的子圖，根據(jù)Kuratowski定理，這個圖是平面圖，由此可得m = O(n)。
現(xiàn)在來分析算法的復雜度。第1步可以利用J. Hopcroft提出的線性時間算法在O(n + m) = O(n)時間內完成。第2步可以用寬度優(yōu)先搜索在O(n)時間內實現(xiàn)。第3步可以直接在O(n)時間內實現(xiàn)。第4步是整個算法的瓶頸。 它需要計算一個O(2^(n/2))的數(shù)值。使用一般的算法實現(xiàn)時間復雜度將為O(n^2)，如果使用快速正交變換實現(xiàn)時間復雜度將為O(nlogn)。綜合以上四個結果，算法的時間復雜度是O(nlogn)。算法的空間復雜度為O(n)。