TopCoder SRM 691 (Div. 2) Medium. Sunnygraphs2

問題

n 頂点のグラフがある。各頂点 i に対して、

• i から a[i] に辺を張る
• i から n に辺を張る

のどちらかを選択できる。このようにして作られた 2ⁿ 通りのグラフのうち、0..n-1 が連結であるようなものの個数を求めよ。

• 1≦n≦50

解法

i から a[i] に普通に辺を張ってみる。このとき矢印を辿ると必ずサイクルに辿り着く。

サイクル外の頂点を一個切り離してみる。これだと非連結になってしまう。

非連結を解消するにはサイクル内の頂点を 1 個切り離すしかない。

サイクル内の頂点を 2 個切り離しても連結のままである。

一個でもサイクル内の頂点を切り離していれば、サイクル外の頂点を切り離しても連結のままである。

サイクル外の頂点数を x、サイクル内の頂点数を y とする。

ここまで分かれば求め方も分かるだろう。x を切り離すか、切り離さないかで場合分けする。

(1) x を切り離すとき
x の切り離し方が 2^x -1 通り、y の切り離し方が 2^y -1 通りなので$(2^x-1)(2^y-1)$ 通り

(2) x を切り離さないとき
y は切っても切らなくてもいいので $ 2^y $ 通り。

最初から連結の場合しか考えてなかったが、当然最初から連結でないものもある。

こういうときは x も y も切り離さないパターンを除外する必要がある。といっても -1 するだけなので大したことはない。

TopCoder SRM 691 (Div. 2) Medium. Sunnygraphs2

Div.2 med にしては難しくない…？