この問題は各頂点 \(v\) に対して \(v\) を削除したときの連結成分の個数を求めれば解くことができ、これは lowlink と呼ばれるアルゴリズムを用いて解くことができます。

与えられるグラフは連結とは限りませんが、簡単のため以下グラフは連結であると仮定します。元問題の連結グラフの場合への帰着は容易です。

グラフの DFS 木を取り、\(ord_v\) を DFS における頂点 \(v\) の訪問順、\(low_v\) を頂点 \(v\) から DFS 木の辺および高々 \(1\) つの後退辺を用いることでたどり着ける頂点 \(u\) に対する \(ord_u\) の最小値とします。元グラフにおいて DFS 木に使用されなかった辺はすべて後退辺となることに注意してください。

結論から述べると、頂点 \(v\) を削除したときのグラフにおける連結成分の個数は以下のようになります。

• \(v\) の子 \(w\) であって、\(ord_v \leq low_w\) を満たすものの個数を \(c\) とおく。
  • \(v\) が根のとき、連結成分は \(c\) 個となる
  • \(v\) が根でないとき、連結成分は \(c+1\) 個となる

以下これを示します。これらはほぼ同様に示すことができるので、\(v\) が根でない場合のみ解説します。ただし、\(v\) が根のときはすべての \(w\) に対して \(ord_v \leq low_w\) を満たすことに注意してください。

\(v\) の親を \(p\) とおきます。

\(v\) の子 \(w\) について、\(ord_v > low_w\) を満たすとき、ある \(u\) が存在して、\(ord_v > ord_u\) かつ \(w\) から DFS 木の辺および後退辺を高々 \(1\) 度用いることで \(w\) から \(u\) にたどり着くことができます。このような \(u\) に対して \(ord_v > ord_u\) から \(u\) は \(p\) の祖先（あるいは \(p\) 自身）なので、\(v\) を削除しても \(u\) と \(p\) が連結であること、および \(u\) と \(w\) が連結であることから \(p\) と \(w\) も連結である状態が保たれます。

一方、\(v\) の子 \(w\) が \(ord_v \leq low_w\) を満たすとします。このとき、\(w\) を根とする部分木の頂点たちは連結です。また、その他のある頂点 \(u\) と連結であるとすると、横断辺が存在しないことから \(v\) の祖先と連結ですが、これは \(ord_v \leq low_w\) に反します。よって、\(v\) を削除すると DFS 木における \(w\) を根とする部分木の頂点が一つの連結成分をなします。

以上を組み合わせることで証明が完了しました。