社区讨论
关于 tarjan 建图常数优化
P4320道路相遇参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mchrn6tv
- 此快照首次捕获于
- 2025/06/29 22:29 8 个月前
- 此快照最后确认于
- 2025/11/04 06:52 4 个月前
注意到在执行 时,如果出现了一个点双,那么新建的方点一定是 的子节点,并且是其他点双内节点的父节点。那么我们直接从父亲向儿子建单向边即可。
代码示例
CPPif(low[v] == dfn[u]) {
g[f[++tot] = u].push_back(tot);
while(q.top() != v) {
g[f[q.top()] = tot].push_back(q.top());
q.pop();
}
g[f[v] = tot].push_back(v);
q.pop();
}
代码更简洁,常数更小~
回复
共 0 条回复,欢迎继续交流。
正在加载回复...