📄️ 图论基础
敲这个笔记主要是为了复习。
📄️ Tarjan 求 LCA
Tarjan 算法可以在 $O(n+m)$ 的时间复杂度下，离线地处理 LCA 查询。其中 $n$ 是节点数量，$m$ 是询问次数。
📄️ Tarjan 求 SCC
Tarjan 算法可以在 $O(n+m)$ 的时间复杂度下求出一个图的 强连通分量。
📄️ Tarjan 求割点和割边
Tarjan 可以在 $O(n)$ 的时间复杂度内求出一个无向图中的割点、割边。
📄️ 最小生成树
最小生成树指的是：从给定图中选定一些边，使得这些边 连通 所有节点，而且边权之和最小。其实这样的定义就暗含了这个子图是一棵树。
📄️ 最短路
最短路分为两种：
📄️ 连通相关问题
首先介绍几个前置概念（关于 DFS 的）。我们在对一个图进行 DFS 时，搜索的路径是一棵树，称为 DFS 生成树。基于此，整个图的边可以分为以下几种：