公式解説とほとんど同一ですが、個人的に分かりやすかった説明を行います。

グラフ \(G\) において頂点 \(v\) の出次数が \(0\) だったとします。すると、\(v\) 及び \(v\) に接続する辺は \(G\) から削除してしまって問題ありません。なぜなら、\(v\) に到達した時点でそれ以上行き先が無く、「いくらでも移動を繰り返せるか」を考える際に \(v\) に到達する意味がないからです。これにより新たに出次数が \(0\) になる頂点が存在すれば、それもまた同じ議論により削除できます。

それ以上削除ができなくなった時、残る全ての頂点は出次数が \(1\) 以上です。どの頂点から始めても、出る辺を選んで進むことでいくらでも移動を繰り返すことができます。したがって、残った頂点の個数が答えになります。

削除の部分は Queue などを用いて実装することができ、時間計算量は \(\Theta(N + M)\) です。