src/Graph/TwoEdgeConnectedComponents.hpp
概要
木上のimos法による二重辺連結成分分解、O(E + V)。
dfs木に含まれる辺の内、後退辺によって挟まれていないものが橋となる。
imos[i] == 0と(i, par)が橋であることが同値になるようにimos法を行い、その辺で区切ることで二重辺連結成分分解している。
参考: https://www.slideshare.net/chokudai/arc039
Verified with
Code
Back to top page