遇到关于连通性问题的困难,求大佬解答,玄关
  • 板块学术版
  • 楼主Zyhx
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/1/31 20:29
  • 上次更新2025/2/1 14:23:21
查看原帖
遇到关于连通性问题的困难,求大佬解答,玄关
1436256
Zyhx楼主2025/1/31 20:29

本蒟蒻在翻阅洛谷深入浅出提高版第12章例题一:P1656时,观看对该题分析与做法时,产生疑问:

问题1:

原文:“在生成树的基础上,额外的边的意义就是将树中的一条链归成同一个集合,有了这个转化,在不断加边的情况下,可以通过并查集维护树中的边双连通块。具体来说,记录每个点所属的集合,并记录每个集合中深度最小的点,成为集合的顶点。在加入一条新的边 (u,v)(u,v) 时,找到这条边对应树中的链,如果两个端点不属于同一个集合,那取深度较大的点 uu ,让该点与其父节点所在集合进行合并,这样做刚好能将链合并,并且不会合并多余的集合,”。

我应该如何理解“在加入一条新的边 (u,v)(u,v) 时,找到这条边对应树中的链,如果两个端点不属于同一个集合,那取深度较大的点 uu ,让该点与其父节点所在集合进行合并”的作用,以及当“如果两个端点不属于同一个集合”的情况下为什么需要“取深度较大的点 uu ,让该点与其父节点所在集合进行合并”?

问题2:

原文:“考虑树上连通块性质:记录其点集 DFSDFS 序最小为 ll ,最大为 rr ,那么其代表一个区间 [l,r][l,r] 。将树分成若干个连通块后,所有的连通块之间代表的区间只有相离和包含两种关系。也就是可以像 DFSDFS 一样用一个栈维护DFS到的点,当一个点是连通块深度最深的点时,弹出栈顶的一段区间就是弹出这个连通块。有了这些性质,可以在一遍DFS中直接求出所有的边双连通分量:维护每个点是否是连通块深度最低的点,即通过树形DP求出第 ii 个节点的子树,通过至多一条非树边能到的深度最低的点的DFS序,记为 lowilow_i 。遍历完一个子树,当发现 lowi>dfnulow_i>dfn_u ,说明节点 vv 后续不会接回点 uu 的祖先上, (u,v)(u,v) 就是一条割边。遍历完毕后,发现 lowu=dfnulow_u=dfn_u 即子树没有非树边能到达自己祖先的时候,就一直弹出栈顶的点,直到在栈中遇到自己为止,表示这些点为一个边双连通分量。”

我应该如何理解“发现 lowi>dfnulow_i>dfn_u ,说明节点 vv 后续不会接回点 uu 的祖先上”与“发现 lowu=dfnulow_u=dfn_u 即子树没有非树边能到达自己祖先的时候,就一直弹出栈顶的点,直到在栈中遇到自己为止,表示这些点为一个边双连通分量”?

因为蒟蒻想尽快赶完S组的内容,多留点时间来练习,便献祭自己的春节准备弯道超车,却遭遇困难。介于春节假期,我的老师都比较忙,没有时间抽空看我的询问与进行解答,在这里跪求逐位大佬帮本蒟蒻答疑解惑!感谢各位大佬花时间为我答疑,我感激不尽!!!

(若侵权请告知,立刻删除)

2025/1/31 20:29
加载中...