题解

思路

在一棵深度优先搜索树中，记 $dfn_u$ 为结点 $u$ 第一次被访问的时间，$low_u$ 为从 $u$ 的子树出发，经过若干树边并至多经过一条返祖边能够到达的最小时间戳。

若树边 $(u,v)$ 满足 $low_v\ge dfn_u$，则从 $v$ 的子树中不能绕过 $u$ 到达 $u$ 的祖先。此时，从当前结点栈中弹出到 $v$ 为止的所有结点，再加入 $u$，恰好得到一个以 $u$ 为边界的点双连通分量。

做法

对每个尚未访问的连通块开始一次深度优先搜索。进入结点时记录时间戳并把结点压入栈中；遍历边时用边的编号区分树边的反向边与平行边，从而正确处理重边。子结点搜索完成后更新父结点的 $low$ 值，并在满足 $low_v\ge dfn_u$ 时取出一个分量。

为避免长度达到 $5\times 10^5$ 的链导致系统递归栈溢出，使用显式栈保存搜索帧。一个没有产生搜索树子结点的搜索根会单独形成一个只含自身的分量，这同时覆盖孤立点以及只有自环的结点。自环不会改变已经存在的分量边界。

输出前将每个分量内部排序，再将全部分量按字典序排序，以获得确定性的标准输出。评测器按集合比较，因此选手可以使用任意合法顺序。

正确性证明

对任意搜索树边 $(u,v)$，若 $low_v<dfn_u$，则 $v$ 的子树存在一条绕过 $u$ 到达 $u$ 祖先的路径，当前分量尚不能在 $u$ 处分割。若 $low_v\ge dfn_u$，删除 $u$ 后，$v$ 的子树无法到达当前栈中更早的部分，因此这些结点不可能与栈中更早的结点同属一个更大的无割点子图；同时，栈中从 $v$ 开始弹出的结点连同 $u$ 由搜索树边和返祖边连成一个不存在内部割点的极大子图，所以它们恰好构成一个点双连通分量。

每条树边只会在其子树完成时接受一次上述判断，每个非根结点也只在所属分量形成时从栈中弹出，因此所有非平凡分量均被得到且不会重复。没有搜索树子结点的根不属于任何这样的分量，把它单独加入后，所有孤立结点和仅含自环的结点也被完整覆盖。故算法输出且仅输出全部点双连通分量。

复杂度

• 时间复杂度：$O(n+m)$，不计输出排序时为严格线性；排序总复杂度不超过 $O((n+m)\log(n+m))$。
• 空间复杂度：$O(n+m)$。