C - Bridge Editorial by maspy


公式解説では時間計算量 \(O(M(N+M))\) の解法が説明されていますが、この問題には時間計算量 \(O(N+M)\) の解法も存在します。

「橋 検出 アルゴリズム」等でググると資料は多く見つかります。

\(O(N+M)\) 時間での橋の列挙は ABC コンテストレベルでは今のところ見かけませんが、上位の問題ではサブアルゴリズムとして要求される場合もあります。上を目指す場合には確認しておくと良いと思います。

関連: https://judge.yosupo.jp/problem/two_edge_connected_components

posted:
last update: