浅说——tarjan

Tarjan陪伴强连通分量，
生成树完成后思路才闪光。
Euler跑过的七桥古塘
让你，心驰神往……

相关连接：

https://big-news.cn/2019/02/07/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F/

https://www.langlangago.xyz/index.php/archives/83/

（特别感谢洛谷，虽然有点小错）

Tarjan是干啥的？

以上摘自百科

你也看不懂，对吧。那看个毛啊！

tarjan说白了三个用：

1.求强连通分量

2.求LCA

3.无向图中，求割点和桥

----------------------------------------------------------------------------------------------------------------------

?强连通分量

1.啥是强连通分量？

百科

这么说吧，强连通是指这个图中每两点都能够互相到达。

强连通分量也就是最大的强连通子图，很easy吧？

如图，有三个强连通分量（1,2,3）&（4）&（5）。

2.怎么求强连通分量？

噫......很明显，通过肉眼可以很直观地看出（1,3）是一组强连通分量，但很遗憾，代码并没有眼睛，所以该怎么判断强连通分量呢？

如果仍是上面那张图，我们对它进行dfs遍历。

可以注意到红边非常特别，因为如果按照遍历时间来分类的话，其他边都指向在自己之后被遍历到的点，而红边指向的则是比自己先被遍历到的点。

如果存在这么一条边，那么我们可以yy一下

从一个点出发，一直向下遍历，然后忽得找到一个点，那个点竟然有条指回这一个点的边！

那么想必这个点能够从自身出发再回到自身

想必这个点和其他向下遍历的该路径上的所有点构成了一个环，

想必这个环上的所有点都是强联通的。

但只是强联通啊，我们需要求的可是强连通分量啊......

比如说图中红色为强连通分量，而蓝色只是强联通图

因此我们只需要知道这个点u下面的所有子节点有没有连着这个点的祖先就行了。

但似乎还有一个问题啊......

我们怎么知道这个点u它下面的所有子节点一定是都与他强联通的呢？

这似乎是不对的，这个点u之下的所有点不一定都强联通

那么怎么在退回到这个点的时候，知道所有和这个点u构成强连通分量的点呢？

开个栈记录就行了

什么？！这么简单？

没错~就是这么简单~

如果在这个点之后被遍历到的点已经能与其下面的一部分点（也可能就只有他一个点）已经构成强连通分量，即它已经是最大的。

那么把它们一起从栈里弹出来就行了。

所以最后处理到点u时如果u的子孙没有指向其祖先的边，那么它之后的点肯定都已经处理好了，一个常见的思想，可以理解一下。

所以就可以保证栈里留下来u后的点都是能与它构成强连通分量的。

似乎做法已经明了了，用程序应该怎么实现呢？

3.怎么码代码？

首先介绍一下辅助数组

……持续更新