社区讨论

一些奇妙的思考

P8435【模板】点双连通分量参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi88atvx
此快照首次捕获于
2025/11/21 10:16
3 个月前
此快照最后确认于
2025/11/21 12:45
3 个月前
查看原帖
如题,注意到将 low[v]>=dfn[u] 换为 low[v]==dfn[u]||low[v]==dfn[v] 一样可以通过本题,想问一下这个改动是否对代码的正确性产生了影响。
我这边有一些分析,但是我不能确定他对不对:
显然,把栈内+割点全部搞进去就好了。
那么,其实会有第二个问题,为什么不是 low[v]==dfn[u] 呢?难道不可以吗?
注意到这个时候,这些点集显然会被 vv 处理,所以到 uu 这里,就剩个光杆司令 vv 了。
所以只会产生只包含 uuvv 的强连通分量,而这个时候 lowv=dfnvlow_v=dfn_v

回复

0 条回复,欢迎继续交流。

正在加载回复...