給出一個(gè)沒有偶圈的簡(jiǎn)單無向圖，求兩個(gè)頂點(diǎn)間路徑的數(shù)目。

老實(shí)說，這個(gè)題目其實(shí)不容易，在正式競(jìng)賽中肯定不屬于送分題。題目的難點(diǎn)在于發(fā)現(xiàn)“沒有偶圈”這個(gè)條件反映的圖的特殊性質(zhì)。

如提示中所說，考慮圖的雙連通分量。首先解釋一下什么是雙連通分量。無向圖中某個(gè)頂點(diǎn)如果被刪除之后，連通分量的數(shù)目增加，那么這個(gè)頂點(diǎn)就叫做割點(diǎn)。無向圖中不包含割點(diǎn)的極大子圖就是雙連通分量。

雙連通分量中任意兩頂點(diǎn)共圈。從這個(gè)性質(zhì)出發(fā)，可以證明：沒有偶圈的簡(jiǎn)單無向圖的所有雙連通分量只能是2階完全圖或奇圈，收縮所有雙連通分量之后得到的圖是樹。這兩個(gè)性質(zhì)意味著，圖中兩個(gè)頂點(diǎn)間的路徑經(jīng)過的雙連通分量的序列是相同的。由此得到一下算法：

1.求出圖的所有雙連通分量；
2.確定從頂點(diǎn)u到頂點(diǎn)v的一條路徑；
3.確定路徑經(jīng)過的雙連通分量的序列；
4.確定序列中是奇圈的雙連通分量的數(shù)目，記為k，則路徑數(shù)為2^k。

在分析上述算法的復(fù)雜度之間，先補(bǔ)充一下圖的另一個(gè)性質(zhì)。因?yàn)閳D中沒有偶圈，所以圖中不包含同胚于5階完全圖或3,3完全二部圖的子圖，根據(jù)Kuratowski定理，這個(gè)圖是平面圖，由此可得m = O(n)。

現(xiàn)在來分析算法的復(fù)雜度。第1步可以利用J. Hopcroft提出的線性時(shí)間算法在O(n + m) = O(n)時(shí)間內(nèi)完成。第2步可以用寬度優(yōu)先搜索在O(n)時(shí)間內(nèi)實(shí)現(xiàn)。第3步可以直接在O(n)時(shí)間內(nèi)實(shí)現(xiàn)。第4步是整個(gè)算法的瓶頸。 它需要計(jì)算一個(gè)O(2^n/2)的數(shù)值。使用一般的算法實(shí)現(xiàn)時(shí)間復(fù)雜度將為O(n²)，如果使用快速正交變換實(shí)現(xiàn)時(shí)間復(fù)雜度將為O(nlogn)。綜合以上四個(gè)結(jié)果，算法的時(shí)間復(fù)雜度是O(nlogn)。算法的空間復(fù)雜度為O(n)。