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

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

啥是强连通分量？

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

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

Tarjan 是怎么搞定的？

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

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

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

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

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

栈的作用是啥？

栈的作用，就是记录当前 DFS 路径上的点。