---
tags: Coding
---
# 簡介
[參考資料](https://alrightchiu.github.io/SecondRound/graph-introjian-jie.html)

### 表示方法

### 儲存方法
無相圖就是每個邊都是雙向的

### 子圖
G1、G2都是子圖 可以自己定義範圍

### 最短路逕

若一條path中，除了起點vertex與終點vertex之外，沒有vertex被重複經過，則稱這條path為simple path。
圖中，path:X-Y-Z即為simple path，path:W-Y-Z-V-W也是simple path，即使W有重複，但是因為分別是起點與終點，所以仍符合定義。而path:Y-X-Y-W就不是simple path，因為第二次經過Y時，Y不是終點。
圖六

### 環狀與樹狀
環狀：有環
樹狀：無還
圖六中的path:W-Y-Z-V-W，稱為directed cycle(有向循環)；

### 權重

### connect
兩個點互相任意在一個圖互通 但中間可以有其他點

**connected ： (undirected graph)**
對任意兩個vertex都存在一條path(中間可以有多個點)連結這兩個vertex，則稱此undirected graph是connected。
1.圖1中，G1中的所有vertex都可以經過一條path到達其他vertex，因此G1為connected。
2.G2中，vertex:X、S、Z分別與vertex:Y、W、T之間皆不存在path，因此G2不是connected。

**connected component：（undirected graph最大的connect component)**
在一個connect的子圖中不能加入任意的邊或是點之後，使子圖還是維持任意兩個點還是connect。稱此subgraph為connected component **(最大集合的connected subgraph)**。
**注意：** component一定要最大的才成立
* 右上方為G1的其中一個subgraph。此subgraph不是connected component，原因在於，再加入vertex:W、T，以及edge:(Y,W)、(Y,T)，也就是變回G1後，仍然維持connected特性，因此這個subgraph並不是「可以維持connected的最大集合」。
換句話說，在一個connected的undirected graph中，只會有一個connected component，就是graph本身。
* G2本身不是connected，而是由兩個connected component組成。
圖1

**strongly connected ： (directed graph)**
對任意兩個vertex都存在一條path(中間可以有多個點)連結這兩個vertex，則稱此undirected graph是connected。
1.圖2中，G3中的所有vertex都可以經過一條path到達其他vertex，因此G3為strongly connected。
2.G4並非strongly connected，例如，雖然path:S-X-T-Z可以從vertex(S)走到vertex(Z)，但是從vertex(Z)卻無法經由任何一條path到達vertex(S)。

**strongly connected component：(directed graph最大的connect component)**
在一個strongly connect的子圖中不能加入任意的邊或是點之後，使子圖還是維持任意兩個點還是strongly connect。稱此subgraph為strongly connected component **(最大集合的strongly connected subgraph)**。
* 圖2中，右上方為G3的其中一個subgraph。此subgraph不是strongly connected component，原因在於，再加入edge:(W,Z)後(也就是變回G3)，仍然維持connected特性，因此這個subgraph並不是「可以維持connected的最大集合」。
如同undirected graph，若一個directed graph本身是strongly sonnected，則本身也是唯一的strongly connected component。
* G4是由三個strongly connected component組成。
圖2

# BFS
## [文章網址](http://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html)
有用到樹的概念，但實作可以不用到指標。

#include <iostream>
#include <vector>
#include <list>
#include <queue>

class Graph{
private:
    int num_vertex;
    std::vector< std::list<int> > AdjList;
    int *color,             // 0:白色, 1:灰色, 2:黑色
        *distance,          // 0:起點, 無限大:從起點走不到的vertex
        *predecessor;       // -1:沒有predecessor, 表示為起點vertex
public:
    Graph():num_vertex(0){};           // default constructor
    Graph(int N):num_vertex(N){        // constructor with input: number of vertex
        // initialize Adjacency List
        AdjList.resize(num_vertex);
    };
    void AddEdgeList(int from, int to);
    void BFS(int Start);
};

void Graph::AddEdgeList(int from, int to){
    AdjList[from].push_back(to);
}

void Graph::BFS(int Start){

    color = new int[num_vertex];
    predecessor = new int[num_vertex];
    distance = new int[num_vertex];

    for (int i = 0; i < num_vertex; i++) {  // 初始化，如圖二(b)
        color[i] = 0;                       // 0:白色;
        predecessor[i] = -1;                // -1表示沒有predecessor
        distance[i] = num_vertex+1;         // num_vertex個vertex, 
    }                                       // 最長距離 distance = num_vertex -1條edge

    std::queue<int> q;
    int i = Start;
    //設定i與j的原因是因為要方便設定起點 不然其實用j就可以了

    for (int j = 0; j < num_vertex; j++) {  // j從0數到num_vertex-1, 因此j會走過graph中所有vertex
        if (color[i] == 0) {                // 第一次i會是起點vertex, 如圖二(c)
            color[i] = 1;                   // 1:灰色
            distance[i] = 0;                // 每一個connected component的起點之距離設成0
            predecessor[i] = -1;            // 每一個connected component的起點沒有predecessor
            q.push(i);
            while (!q.empty()) {
                int u = q.front();                  // u 為新的搜尋起點
                for (std::list<int>::iterator itr = AdjList[u].begin();        // for loop 太長
                     itr != AdjList[u].end(); itr++) {                         // 分成兩段
                    if (color[*itr] == 0) {                // 若被「找到」的vertex是白色
                        color[*itr] = 1;                   // 塗成灰色, 表示已經被「找到」
                        distance[*itr] = distance[u] + 1;  // 距離是predecessor之距離加一
                        predecessor[*itr] = u;             // 更新被「找到」的vertex的predecessor
                        q.push(*itr);                      // 把vertex推進queue
                    }
                }
                q.pop();        // 把u移出queue
                color[u] = 2;   // 並且把u塗成黑色
            }
        }
        // 若一次回圈沒有把所有vertex走過, 表示graph有多個connected component
        // 就把i另成j, 繼續檢查graph中的其他vertex是否仍是白色, 若是, 重複while loop
        i = j;
    }
}

int main(){
    Graph g1(9);    
    // 建立出圖二(a)的Adjacency List
    g1.AddEdgeList(0, 1);g1.AddEdgeList(0, 2);g1.AddEdgeList(0, 3);
    g1.AddEdgeList(1, 0);g1.AddEdgeList(1, 4);
    g1.AddEdgeList(2, 0);g1.AddEdgeList(2, 4);g1.AddEdgeList(2, 5);g1.AddEdgeList(2, 6);g1.AddEdgeList(2, 7);
    g1.AddEdgeList(3, 0);g1.AddEdgeList(3, 7);
    g1.AddEdgeList(4, 1);g1.AddEdgeList(4, 2);g1.AddEdgeList(4, 5);
    g1.AddEdgeList(5, 2);g1.AddEdgeList(5, 4);g1.AddEdgeList(5, 8);
    g1.AddEdgeList(6, 2);g1.AddEdgeList(6, 7);g1.AddEdgeList(6, 8);
    g1.AddEdgeList(7, 2);g1.AddEdgeList(7, 3);g1.AddEdgeList(7, 6);
    g1.AddEdgeList(8, 5);g1.AddEdgeList(8, 6);

    g1.BFS(0);    

    return 0;
}

## 例子
### uva11624
https://zerojudge.tw/ShowProblem?problemid=e699
用queue，然後四個方向用迴圈去跑就可以大幅減短程式碼。

#include <bits/stdc++.h>
#define int long long
#define MAXN 1005

using namespace std;

struct pos {
    int y, x;
    bool if_peo;
    int dis;
};

char maze[MAXN][MAXN];
int step[MAXN][MAXN];
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
queue<pos> que;

int bfs(int h, int w) {
    while (!que.empty()) {
        pos a = que.front();
        que.pop();
        for (int i = 0; i < 4; i++) {
            pos b;
            b.y = a.y + dir[i][0];
            b.x = a.x + dir[i][1];
            b.if_peo = a.if_peo;
            b.dis = a.dis + 1;
            if ((b.y < h && b.y >= 0 && b.x < w && b.x >= 0) && maze[b.y][b.x] != '#' && step[b.y][b.x] == -1) {
                que.push(b);
                step[b.y][b.x] = b.dis;
            } else if ((b.y >= h || b.y < 0 || b.x >= w || b.x < 0) && b.if_peo == 1) {
                return b.dis;
            }
        }
    }
    return 0;
}

void solve() {
    int h, w;
    pos peo;
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> maze[i][j];
            if (maze[i][j] == 'F') {
                que.push((struct pos){i, j, 0, 0});  // c++11以上，(struct pos){i, j, 0, 0}可以直接寫成{i, j, 0, 0}
                step[i][j] = 0;
            }
            if (maze[i][j] == 'J') {
                peo = (struct pos){i, j, 1, 0};
                step[i][j] = 0;
            }
        }
    }
    que.push(peo);
    int sum = bfs(h, w);
    if (sum)
        cout << sum << endl;
    else
        cout << "IMPOSSIBLE" << endl;
}

signed main() {
    int n;
    cin >> n;
    while (n--) {
        memset(step, -1, sizeof(step));
        while (!que.empty()) que.pop();//要記得清空
        solve();
    }
    return 0;
}

# DFS
## [文章網址](http://alrightchiu.github.io/SecondRound/graph-depth-first-searchdfsshen-du-you-xian-sou-xun.html)

predecessor:
   0   1   2   3   4   5   6   7
  -1   0   0   1   3   3  -1   6
discover time:
   0   1   2   3   4   5   6   7
   1   2  10   3   4   6  13  14
finish time:
   0   1   2   3   4   5   6   7
  12   9  11   8   5   7  16  15

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>      // for std::setw()

class Graph{
private:
    int num_vertex;
    std::vector< std::list<int> > AdjList;
    int *color,             // 0:white, 1:gray, 2:black
        *predecessor,
        *discover,
        *finish;
public:
    Graph():num_vertex(0){};
    Graph(int N):num_vertex(N){
        // initialize Adj List
        AdjList.resize(num_vertex);
    };
    void AddEdgeList(int from, int to);
    void BFS(int Start);    // 定義見上一篇文章
    void DFS(int Start);
    void DFSVisit(int vertex, int &time);
};

void Graph::DFS(int Start){
    color = new int[num_vertex];           // 配置記憶體位置
    discover = new int[num_vertex];
    finish = new int[num_vertex];
    predecessor = new int[num_vertex];

    int time = 0;                          // 初始化, 如圖三(b)
    for (int i = 0; i < num_vertex; i++) { 
        color[i] = 0;
        discover[i] = 0;
        finish[i] = 0;
        predecessor[i] = -1;
    }

    int i = Start;
    for (int j = 0; j < num_vertex; j++) { // 檢查所有Graph中的vertex都要被搜尋到
        if (color[i] == 0) {               // 若vertex不是白色, 則進行以該vertex作為起點之搜尋
            DFSVisit(i, time);
        }
        i = j;                             // j會把AdjList完整走過一遍, 確保所有vertex都被搜尋過
    }
}

void Graph::DFSVisit(int vertex, int &time){   // 一旦有vertex被發現而且是白色, 便進入DFSVisit()
    color[vertex] = 1;                         // 把vertex塗成灰色
    discover[vertex] = ++time;                 // 更新vertex的discover時間
    for (std::list<int>::iterator itr = AdjList[vertex].begin();   // for loop參數太長
         itr != AdjList[vertex].end(); itr++) {                    // 分成兩段
        if (color[*itr] == 0) {                // 若搜尋到白色的vertex
            predecessor[*itr] = vertex;        // 更新其predecessor
            DFSVisit(*itr, time);              // 立刻以其作為新的搜尋起點, 進入新的DFSVisit()
        }
    }
    color[vertex] = 2;                         // 當vertex已經搜尋過所有與之相連的vertex後, 將其塗黑
    finish[vertex] = ++time;                   // 並更新finish時間
}

int main(){
    // 定義一個具有八個vertex的Graph
    Graph g2(8);
    // 建立如圖三之Graph
    g2.AddEdgeList(0, 1);g2.AddEdgeList(0, 2); 
    g2.AddEdgeList(1, 3);
    g2.AddEdgeList(2, 1);g2.AddEdgeList(2, 5);
    g2.AddEdgeList(3, 4);g2.AddEdgeList(3, 5);
    // AdjList[4] is empty
    g2.AddEdgeList(5, 1);
    g2.AddEdgeList(6, 4);g2.AddEdgeList(6, 7);
    g2.AddEdgeList(7, 6);

    g2.DFS(0);    // 以vertex(0), 也就是vertex(A作為DFS()的起點

    return 0;
}

# connect component



output:

predecessor:
   0   1   2   3   4   5   6   7   8
  -1   0  -1  -1   1   4   3   5   6
predecessor:
   0   1   2   3   4   5   6   7   8
  -1   0  -1  -1   0   0   3   0   3
Component#1: 0 1 4 5 7 
Component#2: 2 
Component#3: 3 6 8  

// C++ code
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>      // for std::setw()

class Graph{
private:
    int num_vertex;
    std::vector< std::list<int> > AdjList;
    int *color,             // 0:white, 1:gray, 2:black
        *predecessor,
        *distance,          // for BFS()
        *discover,          // for DFS()
        *finish;
public:
    Graph():num_vertex(0){};
    Graph(int N):num_vertex(N){
        // initialize Adj List
        AdjList.resize(num_vertex);
    };
    void AddEdgeList(int from, int to);
    void BFS(int Start);    
    void DFS(int Start);
    void DFSVisit(int vertex, int &time);

    void CCDFS(int vertex);                // 利用DFS 
    void CCBFS(int vertex = 0);            // 利用BFS, 兩者邏輯完全相同
    void SetCollapsing(int vertex);
    void PrintPredecessor();               // 印出predecessor, 供驗証用, 非必要
};

void Graph::SetCollapsing(int current){
    int root;  // root
    for (root = current; predecessor[root] >= 0; root = predecessor[root]);//先游到根源祖先那邊

    while (current != root) {
        int parent = predecessor[current];
        predecessor[current] = root;
        current = parent;
    }
}

void Graph::CCDFS(int vertex = 0){

    DFS(vertex);      // CCDFS與CCBFS只差這行都是為了找爸爸而已
    PrintPredecessor();
    for (int i = 0; i< num_vertex; i++){//對每個點做collapsing
        SetCollapsing(i);
    }
    PrintPredecessor();

    int num_cc = 0;
    for (int i = 0; i < num_vertex; i++) {
        if (predecessor[i] < 0) {
            std::cout << "Component#" << ++num_cc << ": " << i << " ";
            for (int j = 0; j < num_vertex; j++) {
                if (predecessor[j] == i) {
                    std::cout << j << " ";
                }
            }
            std::cout << std::endl;
        }
    }
}

void Graph::CCBFS(int vertex){

    BFS(vertex);
    PrintPredecessor();
    for (int i = 0; i< num_vertex; i++){
        SetCollapsing(i);
    }
    PrintPredecessor();

    int num_cc = 0;
    for (int i = 0; i < num_vertex; i++) {
        if (predecessor[i] < 0) {
            std::cout << "Component#" << ++num_cc << ": " << i << " ";
            for (int j = 0; j < num_vertex; j++) {
                if (predecessor[j] == i) {
                    std::cout << j << " ";
                }
            }
            std::cout << std::endl;
        }
    }
}
void Graph::PrintPredecessor(){
    std::cout << "predecessor:" << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << i;
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << predecessor[i];
    std::cout << std::endl;
}

int main(){
    Graph g3(9);
    g3.AddEdgeList(0, 1);
    g3.AddEdgeList(1, 0);g3.AddEdgeList(1, 4);g3.AddEdgeList(1, 5);
    // AdjList[2] empty
    g3.AddEdgeList(3, 6);
    g3.AddEdgeList(4, 1);g3.AddEdgeList(4, 5);
    g3.AddEdgeList(5, 1);g3.AddEdgeList(5, 4);g3.AddEdgeList(5, 7);
    g3.AddEdgeList(6, 3);g3.AddEdgeList(6, 8);
    g3.AddEdgeList(7, 5);
    g3.AddEdgeList(8, 6);

    g3.CCDFS();
    std::cout << std::endl;
    g3.CCBFS();
    std::cout << std::endl;

    return 0;
}

# strongly connect component

以component的角度來看只要是DAG那每個點的finish順序會是絕對的（以箭頭方向往下遞減）
所以只要找到最大的finish時間
再從反向的圖中做dfs
就一定會做完一個component的dfs才去下一個component的dfs（因為唯一的出口是被指向的 所以走不出去）
=>每棵dfs的樹就是一個strongly connect component

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>      // for std::setw()

class Graph{
private:
    int num_vertex;
    std::vector< std::list<int> > AdjList;
    int *color,             // 0:white, 1:gray, 2:black
        *predecessor,
        *distance,          // for BFS()
        *discover,          // for DFS()
        *finish;
public:
    Graph():num_vertex(0){};
    Graph(int N):num_vertex(N){
        // initialize Adj List
        AdjList.resize(num_vertex);
    };

    int GetColor(int i){return color[i];};              // 取得private data: color
    int GetFinish(int i){return finish[i];};            // 取得private data: finish
    int GetPredecessor(int i){return predecessor[i];};  // 取得private data: predecessor

    void AddEdgeList(int from, int to);

    void BFS(int Start);
    void DFS(int Start);
    void DFSVisit(int vertex, int &time);
    void VariableInitializeDFS();     // 對DFS()需要的資料：color, discover, finish, predecessor
                                      // 進行「配置記憶體」與「初始化」

    void CCDFS(int vertex);           // 吃一個int, 表示起點vertex, 若沒給就從0開始
    void CCBFS(int vertex = 0);
    void SetCollapsing(int vertex);
    void PrintDataArray(int *array);  // 列印出array[]
    void PrintFinish();               // 列印出 finish[]
    void PrintPredecessor();          // 列印出 predecessor[]

    Graph GraphTranspose();           // 產生Transpose of Graph
    void PrintSCCs(int Start = 0);    // 吃一個int, 表示起點vertex, 若沒給就從0開始

    // 利用QuickSort()得到 finish[] 由大致小的vertex順序
    friend void QuickSort(int *vec, int front, int end, int *vec2);
    friend int Partition(int *vec, int front, int end, int *vec2);
    friend void swap(int *x, int *y);
};

void swap(int *x, int *y){
    int temp = *x;
    *x = *y;
    *y = temp;
}
int Partition(int *vec, int front, int end, int *vec2){
    int pivot = vec[end];
    int i = front - 1;
    for (int j = front; j < end; j++) {
        if (vec[j] > pivot) {
            i++;
            swap(&vec[i], &vec[j]);
            swap(&vec2[i], &vec2[j]);
        }
    }
    swap(&vec[i + 1], &vec[end]);
    swap(&vec2[i + 1], &vec2[end]);

    return i + 1;   // 把 i + 1 當成下一個 recurrsive call 的 中間斷點
}
void QuickSort(int *vec, int front, int end, int *vec2){
    if (front < end) {
        int pivot = Partition(vec, front, end, vec2);
        QuickSort(vec, front, pivot - 1, vec2);
        QuickSort(vec, pivot + 1, end, vec2);
    }
}

void Graph::PrintSCCs(int Start){
    // 第一次DFS(), 目的是取得finish[]
    DFS(Start);

    // 顯示 第一次DFS()後的finish[]
    std::cout << "First DFS() on G, finish time:" << std::endl;
    PrintFinish();

    // gT代表Transpose of Graph
    Graph gT(num_vertex);
    gT = GraphTranspose();

    // 矩陣 finishLargetoSmall[] 用來儲存 finish[] 由大至小的vertex順序
    int finishLargetoSmall[num_vertex];
    for (int i = 0; i < num_vertex; i++) {
        finishLargetoSmall[i] = i;
    }
    // QuickSort()會更新 finishLargetoSmall[] 成 finish[] 由大至小的vertex順序
    QuickSort(finish, 0, num_vertex-1, finishLargetoSmall);

    // 列印出 finish[] 由大至小的vertex順序
    std::cout << "finish time Large to Small:" << std::endl;
    PrintDataArray(finishLargetoSmall);

    // 第二次DFS(), 執行在gT上, 先對四個資料「配置記憶體」且「初始化」
    gT.VariableInitializeDFS();
    int time = 0;
    for (int i = 0; i < num_vertex; i++){
        if (gT.GetColor(finishLargetoSmall[i]) == 0) {
            gT.DFSVisit(finishLargetoSmall[i], time);
        }
    }

    // 顯示 第二次DFS()後的finish[]
    std::cout << "Second DFS() on gT, finish time:\n";
    gT.PrintFinish();
    // 顯示 第二次DFS()後的predecessor[]
    std::cout << "predecessor[] before SetCollapsing:\n";
    gT.PrintPredecessor();

    for (int i = 0; i< num_vertex; i++)
        gT.SetCollapsing(i);

    // 顯示 SetCollapsing後的predecessor[]
    std::cout << "predecessor after SetCollapsing:\n";
    gT.PrintPredecessor();

    // 如同在undirected graph中尋找connected component
    int num_cc = 0;
    for (int i = 0; i < num_vertex; i++) {
        if (gT.GetPredecessor(i) < 0) {
            std::cout << "SCC#" << ++num_cc << ": " << i << " ";
            for (int j = 0; j < num_vertex; j++) {
                if (gT.GetPredecessor(j) == i) {
                    std::cout << j << " ";
                }
            }
            std::cout << std::endl;
        }
    }
    std::cout << std::endl;
}
void Graph::VariableInitializeDFS(){
    color = new int[num_vertex];
    discover = new int[num_vertex];
    finish = new int[num_vertex];
    predecessor = new int[num_vertex];

    for (int i = 0; i < num_vertex; i++) {
        color[i] = 0;
        discover[i] = 0;
        finish[i] = 0;
        predecessor[i] = -1;
    }
}
Graph Graph::GraphTranspose(){
    Graph gT(num_vertex);
    for (int i = 0; i < num_vertex; i++) {
        for (std::list<int>::iterator itr = AdjList[i].begin();itr != AdjList[i].end(); itr++) {
            gT.AddEdgeList(*itr, i);
        }
    }
    return gT;
}
void Graph::PrintDataArray(int *array){
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << i;
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << array[i];
    std::cout << std::endl;
}
void Graph::PrintFinish(){
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << i;
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << finish[i];
    std::cout << std::endl;
}
void Graph::PrintPredecessor(){
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << i;
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << predecessor[i];
    std::cout << std::endl;
}

int main(){
    Graph g4(9);
    g4.AddEdgeList(0, 1);
    g4.AddEdgeList(1, 2);g4.AddEdgeList(1, 4);
    g4.AddEdgeList(2, 0);g4.AddEdgeList(2, 3);g4.AddEdgeList(2, 5);
    g4.AddEdgeList(3, 2);
    g4.AddEdgeList(4, 5);g4.AddEdgeList(4, 6);
    g4.AddEdgeList(5, 4);g4.AddEdgeList(5, 6);g4.AddEdgeList(5, 7);
    g4.AddEdgeList(6, 7);
    g4.AddEdgeList(7, 8);
    g4.AddEdgeList(8, 6);

    std::cout << "Vertex(0) as starting point for the First DFS():\n\n";
    g4.PrintSCCs();
    std::cout << "Vertex(3) as starting point for the First DFS():\n\n";
    g4.PrintSCCs(3);

    return 0;
}

output:

Vertex(0) as starting point for the First DFS():

First DFS() on G, finish time:
   0   1   2   3   4   5   6   7   8
  18  17  16   5  14  15  13  12  11
finish time Large to Small:
   0   1   2   3   4   5   6   7   8
   0   1   2   5   4   6   7   8   3
Second DFS() on gT, finish time:
   0   1   2   3   4   5   6   7   8
   8   4   7   6  11  12  18  16  17
predecessor[] before SetCollapsing:
   0   1   2   3   4   5   6   7   8
  -1   2   0   2   5  -1  -1   8   6
predecessor after SetCollapsing:
   0   1   2   3   4   5   6   7   8
  -1   0   0   0   5  -1  -1   6   6
SCC#1: 0 1 2 3 
SCC#2: 5 4 
SCC#3: 6 7 8 

Vertex(3) as starting point for the First DFS():

First DFS() on G, finish time:
   0   1   2   3   4   5   6   7   8
  16  15  17  18  14  13  12  11  10
finish time Large to Small:
   0   1   2   3   4   5   6   7   8
   3   2   0   1   4   5   6   7   8
Second DFS() on gT, finish time:
   0   1   2   3   4   5   6   7   8
   5   6   7   8  12  11  18  16  17
predecessor[] before SetCollapsing:
   0   1   2   3   4   5   6   7   8
   1   2   3  -1  -1   4  -1   8   6
predecessor after SetCollapsing:
   0   1   2   3   4   5   6   7   8
   3   3   3  -1  -1   4  -1   6   6
SCC#1: 3 0 1 2 
SCC#2: 4 5 
SCC#3: 6 7 8