知識(shí)點(diǎn)-Tarjan
強(qiáng)連通分量：在一個(gè)圖的子圖中，任意兩個(gè)點(diǎn)相互可達(dá)，也就是存在互通的路徑，那么這個(gè)子圖就是強(qiáng)連通分量（或者稱為強(qiáng)連通分支）。如果一個(gè)有向圖的任意兩個(gè)點(diǎn)相互可達(dá)，那么這個(gè)圖就稱為強(qiáng)連通圖。
當(dāng)我們實(shí)現(xiàn)基于dfs的Tarjan算法時(shí)，我們用D[i]記錄節(jié)點(diǎn)i被訪問的時(shí)間（別的博客用dfn[i]），用F[i]記錄節(jié)點(diǎn)i或i的子樹最小可以返回到的節(jié)點(diǎn)j的D[j]（別的博客用low[i]）。
讓我們模擬一下dfs的過程，每個(gè)節(jié)點(diǎn)上左邊的是D的值，右邊的是F的值。
首先從節(jié)點(diǎn)1開始往下深搜，每次搜索都更新D值和F值，此時(shí)F值是節(jié)點(diǎn)本身。
當(dāng)搜索到節(jié)點(diǎn)4時(shí)，已經(jīng)無法繼續(xù)搜索。而此時(shí)D值=F值，所以我們可以判定一個(gè)強(qiáng)連通分量（在代碼中，需要借助“棧”來尋找強(qiáng)連通分量中所有節(jié)點(diǎn)），這個(gè)強(qiáng)連通量就是節(jié)點(diǎn)4。
從圖我們也可以看出，節(jié)點(diǎn)4無法到達(dá)其它任意節(jié)點(diǎn)。
