点双联通分量·每日不懂求救
  • 板块学术版
  • 楼主CNCAGN
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/10/9 11:01
  • 上次更新2023/11/2 14:50:23
查看原帖
点双联通分量·每日不懂求救
65161
CNCAGN楼主2023/10/9 11:01

rt 在做完割点之后做了点双联通分量

在 P8435 【模板】点双连通分量 题解里普遍写道:判断“割点” 只需

dfn[u] <= low[v]

而割点的模板题实际上还要分成root点和非root点分别判断

(u == root && cnt > 1) || (u != root && dfn[u] <= low[v])

而实际上如 P8435 点双连通分量 题解中输出的u并不是割点,比如在以下数据下

6 5
1 3
2 4
1 2
4 6
2 3

输出为4 2 1 而实际割点为2 4

请问dfn[u] <= low[v]既然u代表的并不完全是割点 那么实际含义是什么呢?

注:我的点双连通分量程序 我的割点程序

2023/10/9 11:01
加载中...