关于 tarjan 建图常数优化
查看原帖
关于 tarjan 建图常数优化
1402161
XuHenry楼主2025/6/29 22:29

注意到在执行 tarjan(u)tarjan(u) 时,如果出现了一个点双,那么新建的方点一定是 uu 的子节点,并且是其他点双内节点的父节点。那么我们直接从父亲向儿子建单向边即可。

代码示例

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();
}

代码更简洁,常数更小~

2025/6/29 22:29
加载中...