Skip to content

【DFS 生成树】20261004B 配对 笔记 ​

给定一个 n 个点、m 条边的连通无向简单图。图中的边按照输入顺序从 1 到 m 编号,你需要将这 m 条边划分成 m2 对,每对的两条边至少有一个公共端点。n,m≤2×105。

DFS 生成树其实是 tarjan 的内容,low 数组就是基于非树边只会连接节点和其祖先。

然后只要从树底往上,非树边一起配对掉,剩余的 ≤1 条非树边和这个点连向父亲的边配对。

最近更新