注意到在执行 tarjan(u) 时,如果出现了一个点双,那么新建的方点一定是 u 的子节点,并且是其他点双内节点的父节点。那么我们直接从父亲向儿子建单向边即可。
代码示例
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();
}
代码更简洁,常数更小~