题解

思路推导

一条无向边若被删除后会使其所在连通块分裂，就称为桥。删除图中的全部桥后，每个剩余连通块恰好是一个边双连通分量。因此问题可以分成两步：找出所有桥，再忽略桥对端点做合并。

对无向图进行深度优先搜索。记 $dfn_u$ 为顶点 $u$ 首次被访问的次序，$low_u$ 为从 $u$ 的搜索子树出发，经过至多一条返祖边能够到达的最小访问次序。若树边 $(u,v)$ 满足 $low_v>dfn_u$，那么 $v$ 的子树没有其他边连回 $u$ 或 $u$ 的祖先，因此该边是桥；反之它位于某个环上，不是桥。

输入可能含重边，所以搜索时只能跳过当前树边的反向边，不能跳过所有连接父亲的边。自环不会成为桥。

做法

建立每条无向边对应两条有向弧的邻接表。为避免在长链上递归过深，使用显式栈模拟深度优先搜索，并维护每个顶点当前尚未扫描的邻接弧。顶点退栈时把它的 $low$ 值合并到父亲，并按 $low_v>dfn_u$ 判断父子树边是否为桥。

找到全部桥后，初始化并查集。枚举原图中的每条非桥边，合并它的两个端点。最后按并查集根收集顶点并输出各个集合。输出顺序不影响答案。

正确性证明

对任意搜索树边 $(u,v)$，若 $low_v>dfn_u$，则 $v$ 的搜索子树中不存在绕过该边到达 $u$ 或其祖先的边，删除 $(u,v)$ 后两侧不再连通，所以它是桥。若 $low_v\le dfn_u$，则存在从 $v$ 的子树经返祖边回到 $u$ 或其祖先的路径，该路径与树边共同形成环，删除该边后端点仍然连通，所以它不是桥。由此算法准确找出全部桥。

删除全部桥后，同一剩余连通块内任意两点之间仍有路径，且该路径只经过非桥边；并查集会沿这些边把它们合并。不同剩余连通块之间的每条连接边都是桥，不会被合并。因此并查集得到的集合与边双连通分量一一对应，输出正确。

复杂度分析

搜索与并查集合并都只线性扫描顶点和边。时间复杂度为 $O((n+m)\alpha(n))$，空间复杂度为 $O(n+m)$。