淺談強(qiáng)連通分量與拓?fù)渑判虻膽?yīng)用

1、淺談強(qiáng)連通分量與拓?fù)渑判虻膽?yīng)用浙江 唐文斌摘要強(qiáng)連通分量與拓?fù)渑判蚴菆D論中最基礎(chǔ)的算法之一。本文選取了兩個(gè)簡(jiǎn)單但富有代表性的例子，說(shuō)明這兩個(gè)算法在一類圖論問(wèn)題中的應(yīng)用。例一Going from u to v or from v to u? Poj Monthly Special Jiajia&Winds story , problem G (POJ2762)給定一個(gè)有向圖，問(wèn)是否對(duì)于圖中的任意兩點(diǎn)u、v，總是存在u到v可達(dá)或者v到u（下文中將以aàb表示a到b可達(dá)）可達(dá)。圖中點(diǎn)數(shù)不超過(guò)1000，邊數(shù)不超過(guò)6000。算法分析題目描述很簡(jiǎn)單，我們最直觀的想法就是求一個(gè)傳遞閉包，然

2、后對(duì)于任意兩點(diǎn)a、b判斷是否aàb或者bàa。然而在本題中點(diǎn)數(shù)多達(dá)1000，傳統(tǒng)的求傳遞閉包方法Floyd是行不通的。題目中的規(guī)模很小，似乎我們可以枚舉起點(diǎn)s，并且從s開(kāi)始對(duì)圖進(jìn)行一次寬度優(yōu)先搜索，這樣我們可以在O（N*（N+M）時(shí)間內(nèi)求得傳遞閉包。似乎這個(gè)辦法可行，但事實(shí)上，在本題中雖然規(guī)模小，但是數(shù)據(jù)組數(shù)高達(dá)200組，所以這個(gè)方法也是必然超時(shí)的。我們拋開(kāi)傳遞閉包，重新來(lái)看問(wèn)題。題目中問(wèn)是否對(duì)于任意兩點(diǎn)都在至少一個(gè)方向上可達(dá)。那么如果兩個(gè)點(diǎn)u、v，uàv且vàu，它們當(dāng)然是符合要求的。所以我們第一個(gè)想法就是找到一個(gè)點(diǎn)集，該點(diǎn)集內(nèi)所有點(diǎn)兩兩可達(dá)。由于其內(nèi)

3、部?jī)蓛煽蛇_(dá)，所以我們可以將其縮成一個(gè)點(diǎn)，僅保留連向外界的邊，并不會(huì)影響問(wèn)題的本質(zhì)。這個(gè)點(diǎn)集，就是強(qiáng)連通分量。所以我們的第一步操作就是：求圖中所有的極大強(qiáng)連通分量，將每一個(gè)強(qiáng)連通分量縮成一個(gè)點(diǎn)，保留不同分量間的連邊信息，得到一個(gè)新圖。我們對(duì)原圖進(jìn)行強(qiáng)連通分量縮點(diǎn)得到新圖有什么好處呢？在這個(gè)過(guò)程中，我們將一些冗余信息進(jìn)行了處理，得到的新圖具有一個(gè)很重要的性質(zhì)：無(wú)環(huán)（拓?fù)溆行颍Ｒ驗(yàn)槿绻协h(huán)存在，那么這些環(huán)上的點(diǎn)都是互相可達(dá)的，所以它們應(yīng)該同屬于一個(gè)極大強(qiáng)連通分量，將被縮成一個(gè)點(diǎn)。所以我們現(xiàn)在的問(wèn)題就是對(duì)于新圖一個(gè)拓?fù)溆行虻膱D，判斷圖中是否任意兩點(diǎn)是否在至少一個(gè)方向上可達(dá)。如果一個(gè)拓?fù)溆行虻膱D滿足要

4、求，那么它將擁有一些什么性質(zhì)呢？我們先來(lái)看一些小規(guī)模的情況：（1） 如果圖只有一個(gè)點(diǎn)，則必然滿足條件（2） 如果圖中包含兩個(gè)點(diǎn)，那么必須從一個(gè)點(diǎn)到另一個(gè)點(diǎn)有邊相連。不妨設(shè)為aàb（顯然b到a不可達(dá)）。（3） 如果圖中包含3個(gè)點(diǎn)，不妨設(shè)第三個(gè)為c。那么必須滿足càa或者bàc。通過(guò)上面3個(gè)情況的觀察，我們大致就有了一個(gè)猜想：猜想：拓?fù)鋱DG若滿足對(duì)于圖中任意兩點(diǎn)u、v均有uàv或者vàu，則必然存在一條通過(guò)所有點(diǎn)的鏈。證明：設(shè)圖中的節(jié)點(diǎn)數(shù)目為n。當(dāng)n=1時(shí)，圖滿足要求且包含長(zhǎng)度為1的鏈。當(dāng)n=k > 1時(shí)，假設(shè)n=k-1時(shí)猜想成立，即任何滿足

5、條件的圖都存在一條通過(guò)所有點(diǎn)的鏈。由于圖G是拓?fù)溆行虻?，所以我們總可以找到一個(gè)沒(méi)有入度的點(diǎn)x，將點(diǎn)x刪除之后不會(huì)影響圖中其它點(diǎn)對(duì)之間的連通性。由于圖G是滿足要求的，而將x刪除后其它點(diǎn)對(duì)間的連通性并沒(méi)有被影響，則在G中刪除點(diǎn)x后得到的圖G'也滿足要求。由假設(shè)知，G'中存在一條長(zhǎng)度為n-1的鏈，不妨設(shè)這條鏈的起點(diǎn)為v。由于圖G滿足要求且x沒(méi)有入度，所以x必須存在一條路徑到達(dá)v。若x通過(guò)點(diǎn)y到達(dá)v，而v是一條長(zhǎng)度為n-1的有向鏈的起點(diǎn)，則鏈上的vày部分加上yàv部分就形成了一個(gè)圈，與題設(shè)G是拓?fù)溆行虻拿堋９蕏到v直接有邊相連，那么將x連到v的這條邊加入原有路徑

6、中就得到了一條長(zhǎng)度為n的鏈。由歸納可知，對(duì)于任何一個(gè)滿足條件的拓?fù)鋱DG，均存在一條通過(guò)所有點(diǎn)的鏈。問(wèn)題至此，已經(jīng)基本解決了。我們只需要對(duì)當(dāng)前的新圖尋找是否存在通過(guò)所有點(diǎn)的路。這個(gè)過(guò)程只需要DFS即可解決。求極大強(qiáng)連通分量的復(fù)雜度為O(N+M)，判斷是否存在通過(guò)所有點(diǎn)的路的復(fù)雜度也為O(N+M)。所以總時(shí)間復(fù)雜度也是O(N+M)。至此問(wèn)題被完美的解決。例二Pipes in factory International Online Programming Contest 2006 , problem 2給定一個(gè)有向圖G(V,E)，問(wèn)最多能從G圖中刪去多少條邊，且刪了邊之后圖G的連通性不變。規(guī)模：點(diǎn)

7、數(shù)不超過(guò)1000，邊數(shù)不超過(guò)10000。注：關(guān)于題目在附錄中有原題的英文描述，而原題經(jīng)過(guò)抽象就是上面所提到的一個(gè)圖論問(wèn)題。但我認(rèn)為出題者想考察的并不是這個(gè)問(wèn)題，而是一個(gè)另外的類似問(wèn)題的解法。如果上面提到的問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)解決，那么哈密頓回路問(wèn)題可以也多項(xiàng)式時(shí)間內(nèi)解決。試想一個(gè)有向圖存在一個(gè)哈密頓回路，它的充要條件為圖中任意兩點(diǎn)都互相可達(dá)且可以刪掉|E|-|V|條邊且圖的連通性不變。也就是說(shuō)我們可以利用上述問(wèn)題的解在多項(xiàng)式時(shí)間判定一個(gè)有向圖是否存在哈密頓回路，更進(jìn)一步，我們也可以利用上述問(wèn)題的解構(gòu)造出這條哈密頓回路。而眾所周知，哈密頓回路目前仍然找不到確定性的多項(xiàng)式時(shí)間算法，所以上述問(wèn)題也

8、是不可解的。所以我猜測(cè)，出題者想考察的問(wèn)題應(yīng)該是這樣的：給定一個(gè)有向圖G(V,E)，我們可以改造這個(gè)圖G中的連邊得到新圖G，問(wèn)圖G中至少要含有多少邊，才能滿足G的連通性與圖G一致。算法分析仍然是類似于上面一題的想法，我們先來(lái)看圖G中的每一個(gè)強(qiáng)連通分量。對(duì)于一個(gè)強(qiáng)連通分量，我們?nèi)绾螌?duì)其進(jìn)行改造，用最少的邊得到相同的連通性呢？由于一個(gè)強(qiáng)連通分量?jī)?nèi)的點(diǎn)之間是兩兩可達(dá)的，所以最優(yōu)的方法就是讓這個(gè)分量?jī)?nèi)的點(diǎn)構(gòu)成一個(gè)環(huán)，即使用條邊（若=1，則不需要連邊）。類似的，由于強(qiáng)連通分量?jī)?nèi)的點(diǎn)之間都互相可達(dá)，所以我們可以把它們壓縮成一個(gè)點(diǎn)，僅保留于外界的連邊信息，問(wèn)題本質(zhì)不變。我們不妨設(shè)壓縮之后的新圖為G0。所以現(xiàn)

9、在的問(wèn)題就是如何改造一個(gè)這個(gè)拓?fù)溆行虻膱DG0，用最少的邊得到相同的連通性。由于圖G0是拓?fù)溆行虻?，所以我們所要做的就是刪除盡量多的無(wú)效邊，使得仍然保留原有的拓?fù)湫?。而一個(gè)拓?fù)溆行虻膱D中哪些邊是沒(méi)有必要的呢？如下圖：圖中的紅色邊即為無(wú)效邊，我們的目標(biāo)就是找到所有這種無(wú)效邊并且加以刪除。所謂的無(wú)效邊，就是說(shuō)對(duì)于現(xiàn)有的一條邊uàv，我們可以找到另一條通路不經(jīng)過(guò)這條邊從u到v。那么我們就有一個(gè)很直觀的想法就是不斷嘗試刪無(wú)效邊，隨便找一條邊，看看是否能刪，如果能刪就將其刪除。這個(gè)方法看起來(lái)有點(diǎn)玄乎，但其實(shí)是正確的，我們來(lái)看下面一個(gè)性質(zhì)：性質(zhì)一 假設(shè)有當(dāng)前有兩條可以刪除的邊，不妨設(shè)aà

10、b和uàv。我們?nèi)我鈩h一條邊，不會(huì)導(dǎo)致另一條邊變得不能刪除。證明：上述性質(zhì)在普通有向圖中顯然是不成立的，看下面這個(gè)例子：顯然上圖中的兩條紅色邊可以一起被刪除。但是如果我先刪了藍(lán)色邊，則兩條紅邊都不能刪了。但是請(qǐng)注意，我們現(xiàn)在面對(duì)的圖并不是一般的有向圖，而是一個(gè)拓?fù)溆行虻膱D。刪了一條邊aàb之后導(dǎo)致另一條邊uàv不能刪，意味著什么呢？由于刪去aàb之后使得uàv不能刪，而原本u到v存在著第二條通路現(xiàn)在不存在了，所以說(shuō)aàb這條邊是u到v第二條通路上的一部分。因?yàn)閍àb可以被刪除，所以a到b也存在著另一條通路，那么兩部分相接不就

11、可以保證u到v仍然存在第二條通路了么？除非如上圖所示，即uàv也是a到b的另一條通路上的一部分。而這么一來(lái)，a可以到達(dá)u，u可以到達(dá)a，這就與我們的題設(shè)圖拓?fù)溆行?矛盾了。所以我們刪除任何一條邊，都不會(huì)影響到另一條本來(lái)可以本刪除的邊。有了性質(zhì)一，我們就可以直接用上面提到的樸素算法求得解答。但是上面的方法依次枚舉每一條邊，然后檢查去掉這條邊是否仍然連通，時(shí)間復(fù)雜度較大，為。為了優(yōu)化這個(gè)算法，我們不妨來(lái)規(guī)定一個(gè)檢查邊的順序。我們將圖G0進(jìn)行拓?fù)渑判?。建立一個(gè)空?qǐng)DG，按照逆拓?fù)湫?，每次加入一個(gè)點(diǎn)u和從u出發(fā)的所有有向邊。然后檢查當(dāng)前加入的邊集。對(duì)于當(dāng)前一條邊uàv，看看是否可以將

12、其刪除，如果可以刪除那就刪。顯然這樣做仍然是的，盡管因?yàn)闄z查的邊變少常系數(shù)有些變化，但并沒(méi)有影響算法的時(shí)間復(fù)雜度。不過(guò)按照這個(gè)順序處理，我們就可以進(jìn)行一些優(yōu)化。我們是按照逆拓?fù)湫蚣狱c(diǎn)和邊，也就是說(shuō)當(dāng)前G中的兩個(gè)點(diǎn)a、b的連通情況，不可能與尚未添加的點(diǎn)c有關(guān)系。所以我們可以維護(hù)一個(gè)局部的傳遞閉包，記錄每?jī)蓚€(gè)點(diǎn)之間的連通信息。每次我們加了點(diǎn)u之后，判斷一條邊uàv是否可以被刪除只需要檢查是否存在一個(gè)點(diǎn)x，滿足u到x有邊存在且x可以到達(dá)v。對(duì)于每一條邊的檢查，最多是的。檢查所有邊之后，我們可以從u開(kāi)始遍歷一次，最多的時(shí)間就能得到從u出發(fā)到達(dá)其他點(diǎn)的連通信息了。所以總時(shí)間復(fù)雜度不超過(guò)。比上面的方法優(yōu)了很多。到這里，問(wèn)題已經(jīng)基本解決。不過(guò)大家也可以發(fā)現(xiàn)，本題中不能被刪的那些邊與我們熟知的“橋”很類似，所以我們也許可以通過(guò)類似求橋的方法來(lái)進(jìn)行求解，從而得到更優(yōu)的算