如何求出圖中的強(qiáng)連通分支數(shù)？從節(jié)點(diǎn)1啟動(dòng)DFS并將遍歷的節(jié)點(diǎn)添加到堆棧中。當(dāng)u=6，DFN[6]=low[6]時(shí)，發(fā)現(xiàn)一個(gè)強(qiáng)連通分量。在u=V之前，{6}是強(qiáng)連通分量。初始化時(shí)，low[u]=DFN[

如何求出圖中的強(qiáng)連通分支數(shù)？

從節(jié)點(diǎn)1啟動(dòng)DFS并將遍歷的節(jié)點(diǎn)添加到堆棧中。當(dāng)u=6，DFN[6]=low[6]時(shí)，發(fā)現(xiàn)一個(gè)強(qiáng)連通分量。在u=V之前，{6}是強(qiáng)連通分量。

初始化時(shí)，low[u]=DFN[u]=index

返回節(jié)點(diǎn)5，發(fā)現(xiàn)DFN[5]=low[5]，且{5}是反堆棧后的強(qiáng)連通組件。

返回節(jié)點(diǎn)3，繼續(xù)搜索節(jié)點(diǎn)4，并將4添加到堆棧中。發(fā)現(xiàn)節(jié)點(diǎn)4相對(duì)于節(jié)點(diǎn)1有一個(gè)后緣，而節(jié)點(diǎn)1仍然在堆棧中，所以低[4]=1。節(jié)點(diǎn)6已經(jīng)出棧，（4,6）是交叉邊，返回3，（3,4）是分支邊，所以low[3]=low[4]=1。

Low（U）=min{Low（U），DFN（V）}DFN（V），（U，V）是指向堆棧中節(jié)點(diǎn)的背面

繼續(xù)返回節(jié)點(diǎn)1，最后訪問節(jié)點(diǎn)2。訪問側(cè)（2，4），4仍然在堆棧中，所以低[2]=DFN[4]=5。返回1后，發(fā)現(xiàn)DFN[1]=low[1]，堆棧中的所有節(jié)點(diǎn)都被取出，形成一個(gè)連通組件{1，3，4，2}。

到目前為止，算法已經(jīng)結(jié)束。得到了圖中三個(gè)強(qiáng)連通分量{1,3,4,2}，{5}，{6}。

1）該圖是強(qiáng)連通的嗎？

給定一個(gè)圖G=]VO，VL分別稱為該路徑的起點(diǎn)和終點(diǎn)。t中的邊數(shù)稱為t的長(zhǎng)度。當(dāng)V0=VL時(shí)，路徑稱為循環(huán)。在無向圖G中，如果頂點(diǎn)VI和VJ之間有一條路，則VI和VJ是連通的。VI與自身相連。設(shè)d為有向圖。如果通過省略D中邊的方向而得到的無向圖是連通圖，則D稱為弱連通或連通。如果D中任意兩個(gè)頂點(diǎn)中至少有一個(gè)可以到達(dá)另一個(gè)頂點(diǎn)，則D稱為單向連通圖。如果D的任意兩個(gè)頂點(diǎn)是相互可達(dá)的，則D稱為強(qiáng)連通圖。從上面的定義中，我們可以很容易地知道有向圖的強(qiáng)連通圖必須是一個(gè)圈，否則它就不能互相連通。無向圖的連通圖不是環(huán)，但有環(huán)的無向圖必須連通。連通分量是指無向圖中的極連通子圖。有向圖中的最大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。所以我們只需要對(duì)給定的圖進(jìn)行分解。

強(qiáng)連通的連通圖是怎樣的？

顯然，如果你需要穿褲子，你必須先穿內(nèi)衣?？梢哉f，穿褲子要靠穿內(nèi)褲。只有當(dāng)你完成了你的褲子，你才真正完成了你的內(nèi)衣（這與現(xiàn)實(shí)世界的邏輯無關(guān)）。這類似于切換到強(qiáng)連通圖。首先，執(zhí)行DFS以獲得一組按依賴關(guān)系（向外路徑數(shù)）排序的點(diǎn)。那么，反轉(zhuǎn)之后，會(huì)有什么變化呢？什么是不變的？變化：依賴性強(qiáng)的點(diǎn)（更多的外向路徑）變成依賴性強(qiáng)的點(diǎn)（更少的外向路徑）。不變量：強(qiáng)連通塊可以由強(qiáng)連通塊的任意點(diǎn)構(gòu)造。同樣，DFS從最少向外路徑的點(diǎn)開始。如果它能返回到自身，則識(shí)別出一個(gè)獨(dú)立的強(qiáng)連通圖。否則，將安全地刪除無用點(diǎn)，因?yàn)楫?dāng)前點(diǎn)必須在塊中具有最少的路徑。