正題之前唠唠幾句，寫這篇部落格的原因是因為做到了一道圖論題，發現顯然需要縮點解決，但是發現自己圖論中的縮點基本忘完了，同時與之相關的Tarjan求SCC（強連通分量Strong Connected Component）也不記得多少，才想着把圖論當中的Tarjan求SCC複習一遍。
附上Tarjan求割邊割點的學習部落格：https://blog.csdn.net/yanyidu/article/details/79793736
正題：
首先，先交代一大串概念（一定要熟記！）。
1.圖的表示：我們用V表示圖G的頂點的集合，E表示圖G的邊的集合，那麼我們圖G=(V,E)。
2.連通圖：在無向圖中，如果任意兩點間可互相到達則稱該圖為連通圖。
3.子圖：如果存在圖G=(V,E)，G1=(V1,E1)，并且V1,E1分别是V,E的子集，那麼我們稱G1是G的子圖。
4.連通子圖：如果G的子圖是連通圖，則稱該子圖為連通子圖。
5.連通分量與最大連通子圖：無向圖G的最大連通子圖稱為G的連通分量；如果G1是G的連通子圖，将G的任何不在該子圖中的點加入到G1後，G1将不再連通，那麼就稱G1是G的最大連通子圖。
6.強連通圖：在有向圖中，如果任意兩點之間可互相到達，則稱該圖為強連通圖。（強連通圖與連通圖的差別就在于有向圖與無向圖）
7.強連通子圖：如果有向圖G的子圖G1是強連通圖，則稱G1為G的強連通子圖
8.強連通分量與最大強連通子圖：有向圖G的最大強連通子圖稱為G的強連通分量；如果G1是G的強連通子圖，将G的任何不在該子圖的點加入到G1後，G1将不再連通，那麼就稱G1是G的最大強連通子圖。
然後，理清楚上面的一些概念之後我們就開始來講講如何求出一個圖強連通分量的個數（由于我們隻學習如何求出一個圖強連通分量的個數，是以似乎隻需要了解什麼是強連通分量即可？）
也許到了這裡，大家松了一口氣說終于沒有需要記憶的概念了。如果這麼想，那就錯了。接下來我們還要介紹一個圖中的點的DFN值與LOW值。
先搬出DFN與LOW的概念：我們用DFS來周遊一個有向圖，在周遊的過程中，用DFN[I]表示編号為I的節點在DFS過程中的通路序号，用LOW[I]表示節點I及其下方節點（也就是有向邊的終點節點）所能到達的通路序号最小的節點的通路序号，顯然初始DFN[I]=LOW[I]。我們在通過DFS周遊的過程中顯然會得到一棵搜尋樹。在搜尋樹上越上層的節點，顯然DFN的值就越小。周遊過程中如果發現某節點在原圖中有邊連到搜尋樹中自己的祖先節點，就更新LOW值。
沒有懂？那我們來看一下下面的例子。
比如這一張圖：
我們不妨以a為起點開始周遊，于是得到下面的搜尋樹。
在搜尋樹圖中紫色的數字就是每個點的通路順序，也就是對應的DFN值，那麼LOW值呢？
為了加深對于LOW值的了解，我們來簡單模拟一下LOW值的更新：
初始化：LOW[I]=I；
我們從1（a,b,...,h分别對應1,2,...,8）開始搜，1的有向邊的終點2，顯然LOW[2]>LOW[1]，是以不更新LOW[1]，同理從2搜尋到3不更新，一直搜尋到4的有向邊的終點5，這個時候會發現我們并沒有更新任何的LOW值，但是接下來問題就來了。我們根據原圖發現5有一條有向邊終點是3，這個時候我們發現5的這條有向邊連向了自己的某一個最先節點，根據我們上面已經介紹的，就需要更新LOW[5]了，也就是說此時LOW[5]=min(LOW[5],LOW[3])=LOW[3]=3，由于5能夠通過圖中的一條返祖邊到達3，而4可以到達5，于是我們也要更新LOW[4]，也就是LOW[4]=min(LOW[4],LOW[5])=LOW[5]=3。這個時候我們就傳回到了3号點，發現從3号點出發的有向邊已經讨論完了，那麼這個時候就順序傳回到自己的一個沒有讨論完所有有向邊的祖先節點，也就是1号點了。此時1還存在以1為起點的有向邊沒有讨論完，我們順次讨論即可。
此時，我們就已經分析完了整個通過DFS周遊圖的過程了，得到如下的LOW值：
LOW[1]=1,LOW[2]=2,LOW[3]=LOW[4]=LOW[5]=3,LOW[6]=1,LOW[7]=LOW[8]=1
于是我們這個時候花了相當精力在DFN值與LOW值上，那麼這兩個值有什麼用呢？當然是用來幫助我們求目标強連通分量！
DFN值的簡單應用：在一個有根樹上，怎樣用O（1）的時間判斷一個結點X是否是另一個結點Y的祖先？我們隻需要從根節點出發通過DFS周遊整棵樹，并且在周遊的過程中記錄每個節點的DFN值和兒子節點數量就可以了。假設X有K個兒子節點，顯然如果滿足這個條件，那麼X就是Y的祖先節點:
通過上述的介紹，相信不難得出如下結論：
如果一個節點的LOW值小于DFN值，那麼就說明它或其子孫節點有邊連到自己上方的節點
如果一個節點的LOW值等于DFN值，那麼久說明它下方的節點不能走到它上方的節點，也就是說那麼該節點就是一個強連通分量在DFS搜尋樹中的根。
那麼問題就來了： X的子孫節點未必與X處于同一個強連通分量，那麼應該如何找到在X的子孫節點中，有哪些點是與X位于同一個強連通分量當中呢？對于這個問題我們用棧解決就行了。
給出Tarjan求強連通分量的代碼：
//Num記錄已經讨論到了幾個點。
//Scc記錄已經找到的強連通分量的個數
//Ins[I]表示I點是否在棧中，即是否正被讨論當中
//Bel[I]表示I點屬于哪一個強連通分量
stack<LL>S;
void Tarjan(LL X){
DFN[X]=LOW[X]=++Num;
S.push(X);Ins[X]=true;
for(LL Y=1;Y<=N;Y++){
if(Map[X][Y]&&DFN[Y]==0){
Tarjan(Y);
LOW[X]=min(LOW[X],LOW[Y]);
} else if(Map[X][Y]&&DFN[Y]!=0&&Ins[Y]){
LOW[X]=min(LOW[X],LOW[Y]);
}
}
if(DFN[X]==LOW[X]){
++SCC;
Y=S.top();S.pop();Bel[Y]=SCC;
while(X!=Y){
Y=S.top();S.pop();Bel[Y]=SCC;
}
}
}
但是僅僅是這樣的做法其實不能保證讨論完每一個點，因為原圖不一定是一個連通圖，這個時候我們就需要一個調用視窗：
for(LL I=1;I<=N;I++){
if(!Bel[I]){
Tarjan(I);
}
}
至此，我們就講完了如何用Tarjan來求出一個圖的SCC個數以及每個SCC都有哪些點（什麼？你什麼時候講了Tarjan？其實上面整個DFN與LOW相關都是Tarjan算法的一部分）。
上述如有錯誤，恭請請教！