読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

Codeforces Union-Find

http://codeforces.com/contest/659/problem/E

問題概要

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

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

解法

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

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

f:id:pekempey:20160331163953p:plain:w350

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

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

f:id:pekempey:20160331164004p:plain:w350

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

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

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

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