tarjan算法代码

Tarjan算法是一种基于深度优先搜索的强连通分量算法，可以用于解决图论中的许多问题。以下是Tarjan算法的代码实现（以C++为例）：

const int MAXN = 1e5 + 5;
int dfn[MAXN], low[MAXN], scc[MAXN], vis[MAXN], stk[MAXN];
int idx, top, cnt;

void tarjan(int u, vector<int> adj[]) {
    dfn[u] = low[u] = ++idx;
    vis[u] = 1;
    stk[++top] = u;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v, adj);
            low[u] = min(low[u], low[v]);
        } else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        cnt++;
        int v;
        do {
            v = stk[top--];
            vis[v] = 0;
            scc[v] = cnt;
        } while (v != u);
    }
}

void find_scc(int n, vector<int> adj[]) {
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(scc, 0, sizeof(scc));
    memset(vis, 0, sizeof(vis));
    idx = top = cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i, adj);
        }
    }
}

其中，`dfn[i]`表示节点i的搜索次序，`low[i]`表示节点i能够到达的最小搜索次序，`scc[i]`表示节点i所属的强连通分量编号，`vis[i]`表示节点i是否在栈中，`stk[i]`表示当前搜索路径上的节点栈。`find_scc`函数是整个算法的入口，它遍历所有节点，对于未被访问过的节点，调用`tarjan`函数进行搜索。