随便总结下给自己以后回忆，结论全凭感觉加一点点实践，如有错误欢迎指出。 图为单向边 缩点需要vis标记是否在队列 图为无向边 求双边连通，求桥 无重边 深搜不搜爹，递归多传个爹是谁 有重边 深搜不搜同边，链式前向星存图，同边的id差1。或者走爹走两次才行。 求割点 搜不到返祖边即是割点，low[v] >= dfn[u] 求割边 儿子搜不到返回爹的边即割边，low[v] > dfn[u]
本文总结了图算法中的关键概念，包括单向边、无向边的处理方式，以及求解双边连通、桥、割点和割边的技巧。特别讨论了在有重边的情况下，如何通过深搜避免重复搜索，提供了链式前向星存图的方法，并介绍了判断割点和割边的条件。
扫一扫
711
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
