# 利用DFS尋找Strongly Connected Component
## 參考網站
[Graph: 利用DFS尋找Strongly Connected Component(SCC)](http://alrightchiu.github.io/SecondRound/graph-li-yong-dfsxun-zhao-strongly-connected-componentscc.html)
## 步驟
1. 對G做第一次DFS，順序隨便
2. 按照finish陣列將vertex由小到大排序
3. 依照第二步得出的vertex順序，由小到大對G做第二次DFS
4. 按照finish陣列將vertex由小到大排序
5. 依照第四步得出的vertex順序，由大到小對gT做DFS
6. 用步驟五得到的finish陣列即可依照參考網站教學將SCCs分開

***主要是依照這個圖的概念分離SCCs***
（圖片來源：[Graph: 利用DFS尋找Strongly Connected Component(SCC)](http://alrightchiu.github.io/SecondRound/graph-li-yong-dfsxun-zhao-strongly-connected-componentscc.html)）

## Code

#include <iostream>
#include <vector>
#include <string.h>
#include <set>

void DFS(int root, bool* state, int* finish, int* start, std::vector<std::vector<int>>& E, int& findOrder);
void bubbleSort(int* arr, int* cmp_arr, int len);

int main() {
    
    int n;
    std::cin >> n;

    std::vector<std::vector<int>> E;
    std::vector<std::vector<int>> eT;
    int findOrder;
    bool state[n];
    int finish[n], vertexOrder[n], start[n];

    // initialize
    for (int i = 0; i < n; i++) vertexOrder[i] = i;
    for (int i = 0; i < n; i++) {
        std::vector<int> newVector;
        E.push_back(newVector);
        eT.push_back(newVector);
        for (int j = 0; j < n; j++) {
            E[i].push_back(0);
            eT[i].push_back(0);
        }
    }
    int from, to;
    while (std::cin >> from >> to) {
        E[from][to] = 1;
        eT[to][from] = 1;
    }

    
    // 對G做第一次DFS
    findOrder = 1;
    memset(state, 0, sizeof(state));
    for (int i = 0; i < n; i++) // 順序任意
        if (!state[i]) DFS(i, state, finish, start, E, findOrder);

    // 按照finish由小到大排序
    bubbleSort(vertexOrder, finish, n);

    
    // 對G做第二次DFS
    findOrder = 1;
    memset(state, 0, sizeof(state));
    for (int i = 0; i < n; i++) // 按照finish由小到大
        if (!state[vertexOrder[i]]) DFS(vertexOrder[i], state, finish, start, E, findOrder);

    // 按照finish由小到大排序
    bubbleSort(vertexOrder, finish, n);

    
    // 對gT做DFS
    findOrder = 1;
    memset(state, 0, sizeof(state));
    for (int i = n - 1; i >= 0; i--) // 按照finish由大到小
        if (!state[vertexOrder[i]]) DFS(vertexOrder[i], state, finish, start, eT, findOrder);

    // 按照finish由小到大排序
    bubbleSort(vertexOrder, finish, n);

    
    // create SCCs set
    std::vector<std::set<int>> SCCsVertices;
    int back;

    for (int i = 0; i < n; i++) {
        if (i == 0) {
            back = finish[vertexOrder[i]];
            SCCsVertices.push_back(std::set<int>());
            SCCsVertices[SCCsVertices.size() - 1].insert(vertexOrder[i]);
        }
        else if (start[vertexOrder[i]] > back) {
            back = finish[vertexOrder[i]];
            SCCsVertices.push_back(std::set<int>());
            SCCsVertices[SCCsVertices.size() - 1].insert(vertexOrder[i]);
        }
        else SCCsVertices[SCCsVertices.size() - 1].insert(vertexOrder[i]);
    }

    
    // output
    for (int i = 0; i < SCCsVertices.size(); i++) {
        std::cout << "SCC " << i << " : ";
        for (int j : SCCsVertices[i]) std::cout << j << ' ';
        std::cout << '\n';
    }
	
}

void DFS(int root, bool* state, int* finish, int* start, std::vector<std::vector<int>>& E, int& findOrder) {
    state[root] = 1;
    start[root] = findOrder++;
    for (int i = 0; i < E[root].size(); i++) {
        if (E[root][i] == 0) continue;
        if (state[i] == 0) DFS(i, state, finish, start, E, findOrder);
    }
    finish[root] = findOrder++;
}

void bubbleSort(int* arr, int* cmp_arr, int len) {
    for (int i = len; i > 0; i--) {
        for (int j = 0; j < i - 1; j++) {
            if (cmp_arr[arr[j]] > cmp_arr[arr[j + 1]]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}