tarjan算法總結

概念（有向圖中）：

1）在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通。

2）如果有向圖G的每兩個頂點都強連通，則稱G是一個強連通圖。

3）非強連通圖有向圖的極大強連通子圖，稱為強連通分量。

tarjan算法：通過遞歸和棧操作，找強連通子圖，并進行縮點

設每個點的DFS序為dfn[u]，當遞歸到第u個點，發現下一個點v已經被周遊過，且dfn[u]<dfn[v]，這兩個點一定在一個強連通子圖中（構成環）

然後可以用low[u]記錄u所在強連通子圖中最小的DFS序，對于每個強連通子圖，把點都縮為DFS序最小的那個點（即low[u]）

縮點方法：進行遞歸，每次進入函數時都将目前點入棧，每次退出函數時判斷目前點u的DFS序是否為u所在強連通子圖中的最小DFS序，即dfn[u]==low[u]。如果是，那麼就可以将棧中u之後的點全部縮為點u（可以通過vector實作）

#include<bits/stdc++.h>
using namespace std;
const int MX = 1e3 + 5;
stack<int>st;                // 存儲已周遊的結點
int dfn[MX];                 // 深度優先搜尋通路次序
int low[MX];                 // 能追溯到的最早的次序
int mark[MX];                // 檢查是否在棧中(2為在棧中，1為已通路，且不在棧中，0為不在)
vector<int> ver[MX];         // 獲得強連通分量結果
int id[MX];                  // 記錄每個點在第幾号強連通分量裡
int index, sz;               // DFS序，強連通分量個數
struct Edge {
    int v, nxt;
} E[MX*MX];
int head[MX], tot;

void add(int u, int v) {
    E[tot].v = v;
    E[tot].nxt = head[u];
    head[u] = tot++;
}
void init(int n) {
    while (!st.empty()) st.pop();
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    for (int i = 1; i <= n; ++ i) ver[i].clear();
    index = sz = 0;
    memset(head, -1, sizeof(head));
    tot = 0;
}

void tarjan(int u) {
    mark[u] = 2;
    low[u] = dfn[u] = ++ index;
    st.push(u);
    for (int i = head[u]; ~i; i = E[i].nxt) {
        int v = E[i].v;
        if (dfn[v] == 0) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (mark[v] == 2) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        ++ sz;
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            mark[v] = 1;
            ver[sz].push_back(v);
            id[v] = sz;
            if (v == u) break;
        }
    }
}
void solve(int n){
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    init(n);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
    }
    solve(n);
    printf("%d\n", sz);
    return 0;
}