关于边双连通分量的这一段讲解
  • 板块学术版
  • 楼主KS_tips_CN
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/9/25 16:27
  • 上次更新2023/10/27 09:59:40
查看原帖
关于边双连通分量的这一段讲解
427120
KS_tips_CN楼主2022/9/25 16:27

在看洛谷深进的连通性

先讲的是边双联通分量的求法

这里有这样一段,看了好几遍都看不明白,求dl讲解

在(DFS)生成树的基础上,额外的边的意义就是将树上的一条链归成同一个集合。有了这个转化,在不断加边的情况下,可以通过并查集在线地维护树上的边双联通块。具体地,记录每个点所属的集合,并且记录每个集合中深度最小的点,成为集合的顶点。再加入一条新的边(u,v)的时候,找到这条边对应的树上的链,如果链的两端点不属于同一个集合,那么取顶点深度较大的点u,让u和其父节点所在的集合合并

我理解边双联通的意思,也明白时间戳和DFS搜索树,还是有以下几个(很多)问题:

  1. 上一段中使用的并查集,在建好DFS搜索树后的形态是怎样的?

  2. 上一段中提到的链,在加入 (u,v) 这条边的时候,“这条边对应的树上的链”的两端点和 u,v 又有什么区别呢?

  3. 按照 1-2,2-3,1-3 的顺序依次加入边,可以知道此时{1,2,3}是一个边双联通分量,那么在加入边的时候,并查集是怎样改变的?倘若这三步后我又依次加入了 3-4,4-5 两条边,那么可以知道{4},{5}是两个边双联通分量,此时的并查集又是否有改变?

  4. 在序号三中,如果 1-2,2-3 两步中分别将12,23合并,那么在加入 3-4,4-5 这两步中貌似也会将34,45合并,这时候就无法分出来4,5两个边双了,但是如果12,23并没有被合并,那么 1-3 这一步中,由于1,3在两个不同的集合,那么将顶点深度较大的点3和其父节点2合并,那么此时只有23被合并,如何判断{1,2,3}是边双呢?

如果您有时间并且有意愿为我解答,感激不尽

2022/9/25 16:27
加载中...