算法期中1007. 怪獸訓練
有向圖強連通分量
在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。非強連通圖有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。
下圖中，子圖{1,2,3,4}為一個強連通分量，因為頂點1,2,3,4兩兩可達。{5},{6}也分别是兩個強連通分量。
算法期中1007. Tarjan算法計算有向圖強連通分量算法期中1007. 怪獸訓練
Tarjan算法
Tarjan算法是基于對圖深度優先搜尋的算法，每個強連通分量為搜尋樹中的一棵子樹。搜尋時，把目前搜尋樹中未處理的節點加入一個堆棧，回溯時可以判斷棧頂到棧中的節點是否為一個強連通分量。
定義DFN(u)為節點u搜尋的次序編号(時間戳)，Low(u)為u或u的子樹能夠追溯到的最早的棧中節點的次序号。
算法僞代碼
tarjan(u) {
DFN[u]=Low[u]=++Index // 為節點u設定次序編号和Low初值
Stack.push(u) // 将節點u壓入棧中
for each (u, v) in E // 枚舉每一條邊
if (v is not visted) // 如果節點v未被通路過
tarjan(v) // 繼續向下找
Low[u] = min(Low[u], Low[v])
else if (v in S) // 如果節點v還在棧内
Low[u] = min(Low[u], DFN[v])
if (DFN[u] == Low[u]) // 如果節點u是強連通分量的根
repeat
v = S.pop // 将v退棧，為該強連通分量中一個頂點
print v
until (u== v)
}
算法流程示範
從節點1開始DFS，把周遊到的節點加入棧中。搜尋到節點u=6時，DFN[6]=LOW[6]，找到了一個強連通分量。退棧到u=v為止，{6}為一個強連通分量。傳回節點5，發現DFN[5]=LOW[5]，退棧後{5}為一個強連通分量。
算法期中1007. Tarjan算法計算有向圖強連通分量算法期中1007. 怪獸訓練 傳回節點3，繼續搜尋到節點4，把4加入堆棧。發現節點4向節點1有後向邊，節點1還在棧中，是以LOW[4]=1。節點6已經出棧，(4,6)是橫叉邊，傳回3，(3,4)為樹枝邊，是以LOW[3]=LOW[4]=1。算法期中1007. Tarjan算法計算有向圖強連通分量算法期中1007. 怪獸訓練 繼續回到節點1，最後通路節點2。通路邊(2,4)，4還在棧中，是以LOW[2]=DFN[4]=5。傳回1後，發現DFN[1]=LOW[1]，把棧中節點全部取出，組成一個連通分量{1,3,4,2}。算法期中1007. Tarjan算法計算有向圖強連通分量算法期中1007. 怪獸訓練 算法期中1007. Tarjan算法計算有向圖強連通分量算法期中1007. 怪獸訓練 至此，算法結束。經過該算法，求出了圖中全部的三個強連通分量{1,3,4,2},{5},{6}。
可以發現，運作Tarjan算法的過程中，每個頂點都被通路了一次，且隻進出了一次堆棧，每條邊也隻被通路了一次，是以該算法的時間複雜度為O(N+M)。
題目
貝爺的人生樂趣之一就是約戰馬會長. 他知道馬會長喜歡和怪獸對決，于是他訓練了N隻怪獸，并對怪獸用0到N-1的整數進行編号. 貝爺訓練怪獸的方式是讓它們一對一互毆. 兩隻怪獸互毆會發生以下三種可能的結果：
1） 什麼事也沒發生
2） 第一隻怪獸永遠消失
3） 第二隻怪獸永遠消失
怪獸們經過了曠日持久的互毆. 貝爺不知道哪些怪獸進行了互毆也不知道它們互毆的順序，但他确信無論經過多少次互毆，總有一些怪獸能存活下來，他将要派這些怪獸去和馬會長對決. 現在他想知道至少有多少隻怪獸能存活下來，你能幫他算出來嗎？
請實作下面Solution類中的minLeftMonsters函數，完成上述功能.
參數G: N*N（1 <= N <= 50）字元矩陣，G[i][j]表示怪獸i和怪獸j互毆會發生的結果. 字元‘+’代表怪獸i會消失，’-’代表怪獸j會消失，數字’0’則代表什麼都沒發生. 輸入保證G[i][i]一定是’0’，而且G[i][j]和G[j][i]一定相反（’-’和’+’互為相反，’0’和自身相反）.
傳回值：怪獸存活的最少數目.
例1：
G =
0+-
-0+
+-0
傳回1.
例2：
000
000
000
傳回3.
解題分析
這道題是讓我們計算在經過多次無序的互毆之後、怪物存活的最少數量。那我們來怎麼思考這個問題呢？
其實我們可以把怪物抽象成一個個節點，然後把怪獸消失的動作抽象成一條條有向路徑，這樣的話，我們就可以得到一個有向圖，表示怪物之間互毆的結果。
很明顯，這樣的話，如果若幹隻怪物是互斥的，即若幹個節點構成一個環，那麼這幾隻怪物最後存活的數量最少為1，剛好是環的個數，也即計算強連通分量的個數。
這樣我們就可以通過上面提到的Tarjan算法的思想來解決這個問題，在此就不再贅述~
源代碼
class Solution {
public:
int STACK[], top; //Tarjan 算法中的棧
bool InStack[]; //檢查是否在棧中
int DFN[]; //深度優先搜尋通路次序
int Low[]; //能追溯到的最早的次序
int ComponetNumber; //有向圖強連通分量個數
int Index; //索引号
vector <int> Edge[]; //鄰接表表示
vector <int> Component[]; //獲得強連通分量結果
int minLeftMonsters(vector<vector<char>> G) {
top = ComponetNumber = Index = ;
memset(STACK, -, sizeof(STACK));
memset(InStack, , sizeof(InStack));
memset(DFN, -, sizeof(DFN));
memset(Low, -, sizeof(Low));
for (int i = ; i < ; i++) {
while (!Edge[i].empty()) {
Edge[i].pop_back();
}
while (!Component[i].empty()) {
Component[i].pop_back();
}
}
for (int i = ; i < G.size(); i++) {
for (int j = ; j < G[i].size(); j++) {
if (G[i][j] == '+') {
Edge[i].push_back(j);
}
}
}
for (int i = ; i < G.size(); i++) {
if (DFN[i] == -) {
Tarjan(i);
}
}
return ComponetNumber;
}
void Tarjan(int i) {
int j;
DFN[i] = Low[i] = Index++;
InStack[i] = true;
STACK[++top] = i;
for (int edge = ; edge < Edge[i].size(); edge++) {
j = Edge[i][edge];
if (DFN[j] == -) {
Tarjan(j);
Low[i] = min(Low[i], Low[j]);
}
else if (InStack[j]) {
Low[i] = min(Low[i], DFN[j]);
}
}
if (DFN[i] == Low[i]) {
ComponetNumber++;
do {
j = STACK[top--];
InStack[j] = false;
Component[ComponetNumber].push_back(j);
} while (j != i);
}
}
};
以上是我對這道問題的一些想法，有問題還請在評論區讨論留言~