本文介绍了有向图的强连通分量、桥边和割点的概念，以及如何使用Tarjan算法进行求解。在DFS过程中，文章详细阐述了dfs时间戳、搜索树、前向边、后向边和横向边等概念，以及low数组的作用。同时，针对强连通分量、桥边和割点，文章分别讲述了它们的判断标准和求解方法。最后，列举了一些相关的编程题目供读者实践。
强连通分量是啥？
有向图的连通分量是有向图的一个子图，对于子图中任意一个有序点对 (u,v) ，总存在一条从u到v的路径。特殊地，一个点也算一个连通分量。而强连通分量就是一个极大连通分量。
桥和割点好像有点相似之处
无向图的桥边是指一条去掉它之后整个图会变得不连通的边，而无向图的割点就是一个去掉它之后整个图会变得不连通的点。。。好相似啊有没有= =。。有向图里面实际上也有桥和割点，概念和上面是一样的。然而ATP没有好好看有向图跟无向图有什么区别，所以下面提到的桥边和割点仅限于无向图啦。
一些简单的概念
要理解tarjan求这些玩意儿的过程，首先要介绍几个在DFS中的名词儿：
- dfs时间戳：也叫dfs序，存储的是这个节点在dfs的过程中被访问的顺序。
- 搜索树：在dfs中如果限制每个节点只能被访问一次，那么除了第一个访问的点以外&#x
最低0.47元/天 解锁文章
扫一扫
529
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
