社区讨论

关于 tarjan 建图常数优化

P4320道路相遇参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@mchrn6tv
此快照首次捕获于
2025/06/29 22:29
8 个月前
此快照最后确认于
2025/11/04 06:52
4 个月前
查看原帖
注意到在执行 tarjan(u)tarjan(u) 时,如果出现了一个点双,那么新建的方点一定是 uu 的子节点,并且是其他点双内节点的父节点。那么我们直接从父亲向儿子建单向边即可。
代码示例
CPP
if(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 条回复,欢迎继续交流。

正在加载回复...