边双连通

DFS找桥并判断边双连通

首先，对原图进行 DFS。

如上图所示，黑色与绿色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径，我们说这条非树边 覆盖 了这条树上路径上所有的边。绿色的树边 至少 被一条非树边覆盖，黑色的树边不被 任何 非树边覆盖。

我们如何判断一条边是不是桥呢？显然，非树边和绿色的树边一定不是桥，黑色的树边一定是桥。

如何用算法去实现以上过程呢？首先有一个比较暴力的做法，对于每一条非树边，都逐个地将它覆盖的每一条树边置成绿色，这样的时间复杂度为 。

怎么优化呢？可以用差分。对于每一条非树边，在其树上深度较小的点处打上 -1 标记，在其树上深度较大的点处打上 +1 标记。然后 求出每个点的子树内部的标记之和。对于一个点u其子树内部的标记之和等于覆盖了u和u的父亲p之间的树边的非树边数量。若这个值非0，则u和u的父亲p之间的树边不是桥，否则是桥。

用以上的方法 求出每条边分别是否是桥后，两个点是边双连通的，当且仅当它们的树上路径中不包含桥。

意思是dfs然后顺带打上差分，再dfs顺带求出子树内部标记之和（dfs记录子树大小然后dfs序前缀和作差），把这个和标记在u节点上，那么除了根节点以外每个节点都指定一条树边。最后跑一次树剖验证路径和为0。

点双连通

DFS 找割点并判断点双连通

如上图所示，黑色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径。

考虑一张新图，新图中的每一个点对应原图中的每一条树边（在上图中用蓝色点表示）。对于原图中的每一条非树边，将这条非树边对应的树上简单路径中的所有边在新图中对应的蓝点连成一个连通块（这在上图中也用蓝色的边体现出来了）。

这样，一个点不是桥，当且仅当与其相连的所有边在新图中对应的蓝点都属于同一个连通块。两个点点双连通，当且仅当它们在原图的树上路径中的所有边在新图中对应的蓝点都属于同一个连通块。

蓝点间的连通关系可以用与求边双连通时用到的差分类似的方法维护，时间复杂度O(n+m)。