SRM419 Div2 1000

問題

頂点サボテンとは、2つ以上単純サイクルに属する頂点がない無効グラフである。単純サイクルとは、2回以上同じ頂点を通らないようなサイクルを言う。頂点数nと辺集合edgesが与えられる。頂点サボテンであるような連結成分の個数を返す。

考え方

まず、edgesから隣接行列に直しておく。
dfsで、その頂点が単純サイクルにいくつ属しているかを計算する。
通った頂点のフラグをどんどん消していって、いくつその頂点に戻ってこれるか。
最初の頂点から次の頂点行ってすぐに戻るような辺は考えない。
もし、単純サイクルに2つ以上属する場合はその辺は使えない。
Union-Findで連結成分を計算し、すべての頂点のルートをsetに入れる。
あとは、そのsetで、上で調べた2つ以上属している頂点のルートを削除。
setのサイズが答えになる。