社区讨论
一些奇妙的思考
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] 呢?难道不可以吗?
注意到这个时候,这些点集显然会被 处理,所以到 这里,就剩个光杆司令 了。
所以只会产生只包含 和 的强连通分量,而这个时候 。
回复
共 0 条回复,欢迎继续交流。
正在加载回复...