主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
Tarjan
最后更新于 2025-07-31 10:55:45
作者
UniGravity
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
每次比赛前都想着要复习 tarjan，所以直接写一篇之后就不用找了。 ### 强连通分量 有向图。即这个分量的每个点都能到达其它点。 判断方式是 $low_x\ge dfn_x$ 代表连不出去，然后跳栈直到跳到 $x$，因为 $x$ 是这个分量中 $dfn$ 最小的了。 细节是注意跳栈时要把 $vis$（是否在栈内）设成 $0$，防止重复访问已经更新的点。所以必须先判断在栈内再 $low_x\gets\min(low_x,dfn_y)$ 缩完强连通分量后是一个 DAG。 ### 点双连通分量 无向图。即删去这个分量内任意一点这个分量仍然连通。 值得注意的是，一个点可能会被塞在很多个点双里面。 所以我们统计分量不在最后统计而是在 $dfs$ 完子树 $y$ 后更新，同时弹栈只需要弹到 $y$，$x$ 加入但是不能从栈中弹出。 这个可能需要记录一下上一个弹的是什么点，判断是否有 $lst\neq y$。 是点双的条件是 $low_y\ge dfn_x$，原因是即使连到了把 $x$ 删掉也没用。 第二个细节是需要特判当前是根且独立子树数量 $\ge 2$ 的情况。此时点双里面就这一个点。 ### 边双连通分量 无向图。删去分量内任意一边仍然连通。 当有重边的时候不能只记父亲，因为重边只会删掉某一条。正确的做法是记录来的边的编号。 然后在最后面判断 $low_x\ge dfn_x$ 更新即可。跳的时候记得把 $x$ 加进去。 ### 割点 无向图。删去这个点图不连通。 还是在枚举子树 $y$ 时判断是否有 $low_y\ge dfn_x$。 分成根和普通点，根的话就是独立子树 $\ge 2$。 ### 割边 / 桥 无向图。删去这个边图不连通。 和割点一样，但是枚举子树 $y$ 变成了 $low_y>dfn_x$，原因是如果能到 $x$ 说明不是割边。 同时不能记父亲要记来的边的编号。
正在渲染内容...
点赞
0
收藏
0
