这是我基础图论知识的一块漏洞，现在补上~~

先来看割点的定义：

对于无向图$G$，如果删除某个点$u$后，连通分量数目增加，则称点$u$是图$G$的割点。

怎样求出一个图所有的割点呢？不难想到一个$O(n(n+m))$的做法，但这显然不是最优的，考虑其他思路。

我们考虑一个无向图的DFS树，发现无向图中的边只可能是树边或是由子孙连向祖先的反向边。画个图更清楚：

上图是一个无向图，我们画出它的DFS树：

我们想一想，割点可能会具有怎样的性质？为了方便描述，我们把在某点$a$的子树中(不包括$a$)的点集记为$S(a)$，把不在$a$的子树中的点集记作$T(a)$。观察上图中的点2，如果我们将它删除，那$S(2)$中的4和$T(2)$依然连通，删除2对它没有影响；但是$S(2)$中的5和$T(2)$由于2的消失变得不连通，图的连通分量个数增加，因此点2是该图的一个割点。

分析一下思路，我们可以得到这样一个结论：

对于某点$u$，若$S(u)$中存在至少一点$v$，满足$v$与$T(u)$之间没有任何边，则$u$是割点。

具体实现上，我们可以记录DFS过程中结点第一次访问的时间$pre[u]$，以及结点及其后代所能连回的最早的祖先的$pre$值$low[u]$。于是问题转化成求某一结点是否存在一个儿子$v$使得$low[v] \ge pre[u]$。解决这个问题，我们只需DFS全图一次即可，总复杂度$O(n+m)$。

再来研究一下桥，先来看定义：

对于无向图$G$，如果删除某条边$(u,v)$后，连通分量数目增加，则称边$(u,v)$是图$G$的桥。

判断割点和桥大致过程是一样的，都是基于DFS的思想。不同之处在于，由于删除的是一条边，所以结论需要稍微改动：

对于某树边$(u,v)$，设$u$是$v$的父亲，若$S(v) \cup \{v\}$中存在至少一点$k$，满足$k$与$T(u) \cup \{u\}$除$(u,v)$外没有任何边，则$(u,v)$是桥。对于所有非树边$(u,v)$，一定不是桥。

转化一下条件，就是对于某一结点$u$，求它的每个儿子$v$是否有$low[v]>pre[u]$，如果是，则$(u,v)$是桥。求桥和求割点复杂度相同，同样是$O(n+m)$。