Codeforces Round #346 (Div. 2) E. New Reform

無向グラフが与えられる。このグラフは連結とは限らない。

それぞれの辺に向きをつけたとき、入次数が 0 の頂点の個数は最小でいくつになるだろうか。

グラフが連結のときを考えよう。

グラフに閉路がない、つまり木であるとき、適当な頂点を根として有効辺を貼れば入次数が 0 の頂点の個数は 1 個にできる。0 個にはさすがにできない。

グラフに閉路があるとき、うまく構成すれば入次数が 0 の頂点の個数を 0 個にできる。

（追記）グラフのいくつかの辺を使って木を構成すれば入次数 0 の頂点は 1 つだけにできて、木の根を閉路の中の頂点にすれば入次数 0 の頂点を消せる。

今回は複数の連結成分があるので、各連結成分が木であるかを判定すればいい。

木であるかを判定するには、（辺の数）=（頂点数)-1 であるかを見るだけで十分である。

最初グラフが連結だと思って 3 行くらいのコードを投げてしまった。