Tarjan算法如何巧妙地解决连通分量问题？

一句话概括... 要说图论里最让人头大的问题，那必须是连通分量了。特别是强连通分量，那个绕来绕去的结构，真的能把人绕晕。不过呢， 有个叫 Tarjan 的大佬，他搞出来一个算法，叫 Tarjan 算法，专门用来解决这类问题。说实话，这算法刚看的时候也挺吓人，一堆数组、一堆栈，还有各种 low、dfn，看着就头大。但你一旦搞懂了就会觉得——哎哟，这玩意儿真牛！

啥是强连通分量？

咱先从头说起。啥叫强连通？就是图里两个点，能互相走到对方，那它们就是强连通的。如果一个图里所有点都能互相走到，那这个图就是强连通图。 我整个人都不好了。 但现实中的图，往往不是这么完美的。有些点能互相走，有些点就只能单向走。这时候，我们就把那些能互相走到的点，组成一个“强连通分量”。

举个例子， 你在一个城市里开车，有些地方你随便开，都能绕回来那这些地方就组成了一个强连通分量。但有些地方，你一进去就出不来了那它就不是强连通的。害，现实就是这么残酷，调整一下。。

Tarjan 是怎么搞定的？

C位出道。 那 Tarjan 是怎么把这些强连通分量找出来的呢？他用的是 DFS，然后配合一个栈。这个栈的作用，就是记录我们走过的路径。每当我们走到一个点，就把它压进栈里。然后我们继续往下走，直到走到一个“尽头”——也就是不能再往下走了。

这时候，我们就看看这个点能不能回到它之前走过的点。如果能，那说明它和之前的点在一个强连通分量里。 我满足了。 如果不能，那它就是一个新的强连通分量的起点。

这里有两个关键数组：dfn 和 low。

• dfn记录每个点被访问的时间戳，也就是第几个被访问的。
• low记录这个点能回溯到的最早的祖先节点的时间戳。

我跪了。 你懂的，这两个数组就是 Tarjan 算法的灵魂。它们帮我们判断一个点是不是在一个强连通分量里。

栈的作用是啥？

栈的作用，就是记录当前 DFS 路径上的点。当我们发现一个强连通分量时就把栈里属于这个强连通分量的点都弹出来。这样，我们就能把图里的所有强连通分量都找出来。

来一波... 举个例子，假设我们从点 A 开始 DFS，走到点 B，再走到点 C。这时候我们发现 C 能回到 A，那 A、B、C 就在一个强连通分量里。这时候，我们就把栈里的 A、B、C 都弹出来组成一个强连通分量。

代码实现

来看一段代码， 你就明白了：

void tarjan {
    dfn = low = ++index;
    st.push;
    vis = 1;
    for ; i++) {
        int v = g;
        if  {
            tarjan;
            low = min;
        } else if  {
            low = min;
        }
    }
    if  {
        int v;
        do {
            v = st.top; st.pop;
            vis = 0;
            color = scc_cnt;
        } while ;
        scc_cnt++;
    }
}

总结一下。 这段代码看着复杂，其实逻辑挺清晰的。我们从一个点开始 DFS，记录 dfn 和 low，然后不断往下走。一旦发现一个强连通分量，就把栈里的点都弹出来组成一个强连通分量。

缩点是啥意思？

缩点，就是把一个强连通分量看成一个点。这样，原来的图就变成了一个 DAG。 求锤得锤。 这在很多图论题里特别有用，比如求最长路径、最短路径啥的。

举个例子，假设你在一个城市里开车，有些地方你随便开都能绕回来。那我们就可以把这些地方看成一个“超级点”， 地道。 然后在这个“超级点”之间建边。这样，问题就简化了。

割点和桥

妥妥的！ 除了强连通分量，Tarjan 算法还能用来找割点和桥。割点就是图里一个点，如果把它删了图就变成两个部分。桥就是图里一条边，如果把它删了图也变成两个部分。

找割点和桥的思路，其实和找强连通分量差不多。我们还是用 DFS，记录 dfn 和 low。 栓Q！ 然后判断一个点是不是割点，或者一条边是不是桥。

百感交集。 比如 如果一个点的子节点的 low 值大于等于这个点的 dfn 值，那这个点就是割点。如果一条边的子节点的 low 值大于这个边的 dfn 值，那这条边就是桥。

为啥 Tarjan 这么牛？

主要原因是 Tarjan 算法的时间复杂度是 O，也就是点数加边数。这在图论里已经是很优秀的复杂度了。而且它能一边解决强连通分量、割点、桥这些问题，简直是一箭多雕。

说实话，Tarjan 算法刚学的时候确实有点绕。但你一旦搞懂了就会觉得——哎哟，这玩意儿真牛！

一下

所以Tarjan 算法到底牛在哪？

它能用一次 DFS，搞定强连通分量、割点、桥这些图论里的经典问题。而且时间复杂度还特别优秀。你说牛不牛？

咱就是说学图论不学 Tarjan，就像吃火锅不蘸麻酱， 说真的... 总觉得缺点啥。害，赶紧学起来吧！