在算法的世界里，强连通图是一个非常重要的概念，它描述的是一个有向图中任意两点都可以互相到达的情况。而Tarjan算法则是解决这一问题的经典方法之一！🚀

首先，我们需要了解什么是强连通分量（SCC）。简单来说，就是将图中所有可以互相到达的点划分到同一个集合中。Tarjan算法通过深度优先搜索（DFS）实现，其核心在于利用栈来记录访问路径，并通过低链接值(low-link value)判断是否构成一个完整的强连通分量。

具体步骤如下：

1️⃣ 从图中的某个节点开始遍历；

2️⃣ 每次递归时更新当前节点的low值；

3️⃣ 当发现某个节点的low值等于其dfn值时，说明找到了一个新的强连通分量。

💡示例代码如下：

```cpp

void tarjan(int u) {

dfn[u] = low[u] = ++timestamp;

st.push(u);

in_stack[u] = true;

for (auto &v : adj[u]) {

if (!dfn[v]) {

tarjan(v);

low[u] = min(low[u], low[v]);

} else if (in_stack[v]) {

low[u] = min(low[u], dfn[v]);

}

}

if (low[u] == dfn[u]) {

// 找到一个新SCC

while (st.top() != u) {

in_stack[st.top()] = false;

st.pop();

}

in_stack[u] = false;

st.pop();

}

}

```

通过Tarjan算法，我们可以高效地解决各种与强连通图相关的问题，比如缩点建模等。💖

算法 图论 Tarjan