# Tarjan 演算法

## 無向圖，算 low 及 dfn，找割點與橋
- [1192. Critical Connections in a Network](https://leetcode.com/problems/critical-connections-in-a-network/)
- `dfn` : 每個點在 dfs 的順序
- `low` : 只用一個回邊，所能走到的最小 dfn 數值

    vector<int> G[1000];
    int low[1000], dfn[1000], idx = 1;

    void dfs(int now, int parent){
        low[now] = dfn[now] = idx++;
        for(auto &nb:G[now]){
            if(nb == parent)    continue; //避免重複走同一個邊
            
            if(dfn[nb] == 0){ // tree edge
                dfs(nb, now);
                low[now] = min(low[now], low[nb]);
                // if(now != root && low[nb] >= dfn[now]) -> AP
                // if(low[nb] > dfn[now]) -> bridge
            } else {          // back edge
                low[now] = min(low[now], dfn[nb]);
            }
        }
        // if(now == root && child >= 2) -> AP
    }

- [點雙連通分量](https://ideone.com/7F3nvS) : 用割點分割圖，子圖中的點互相走的到
- [邊雙連通分量](https://ideone.com/wgh2S4) : 用橋分割圖，子圖中的點互相走的到
## 有向圖，找強連通分量(SCC)
- 有向圖，[強連通分量](https://ideone.com/e2Zfxh)的點互相走的到
- 方法一: `Tarjan's Algorithm`
- 透過 `Stack` 紀錄正在處理的 vertex
- 透過 `inStack` 排除 `forword edge` 及 `cross edge`

    void dfs(int now){
        low[now] = dfn[now] = idx++;
        Stack.push(now);
        inStack[now] = true;
        for(auto &nb:G[now]){
            if(dfn[nb] == 0){         // tree edge
                dfs(nb);
                low[now] = min(low[now], low[nb]);
            } else if (inStack[nb]) { // back edge
                low[now] = min(low[now], dfn[nb]);
            }
        }

        if(low[now] == dfn[now]) {
            while (Stack.top() != now){
                int tmp = Stack.top();  Stack.pop();
                BCC[bcnt].push_back(tmp);
                inStack[tmp] = false;
            }
            bcnt++;
        }
    }

- 方法二: `Kosaraju Algorithm`
- 先對反向圖跑一次 DFS，紀錄 `離開 DFS 的時間`
- 由離開時間大到小對原圖跑 DFS，走的到的地方形成 `SCC`

    void rdfs(int now){
        rDone[now] = true;
        for(auto &nb:rG[now])
            if(!rDone[nb])
                rdfs(nb);
        order.push_back(now);
    }

    void dfs(int now){
        done[now] = true;
        BCC[bcnt].push_back(now);
        for(auto &nb:G[now])
            if(!done[nb])
                dfs(nb);
    }

    void Kosaraju(){
        for(int i=0;i<n;i++)
            if(!rDone[i])
                rdfs(i);

        reverse(order.begin(),order.end());

        for(auto i:order){
            if(!done[i]){
                bcnt++;
                dfs(i);
            }
        }
    }