TopCoder SRM 691 (Div. 2) Medium. Sunnygraphs2
問題
n 頂点のグラフがある。各頂点 i に対して、
- i から a[i] に辺を張る
- i から n に辺を張る
のどちらかを選択できる。このようにして作られた 2n 通りのグラフのうち、0..n-1 が連結であるようなものの個数を求めよ。
- 1≦n≦50
解法
i から a[i] に普通に辺を張ってみる。このとき矢印を辿ると必ずサイクルに辿り着く。
サイクル外の頂点を一個切り離してみる。これだと非連結になってしまう。
非連結を解消するにはサイクル内の頂点を 1 個切り離すしかない。
サイクル内の頂点を 2 個切り離しても連結のままである。
一個でもサイクル内の頂点を切り離していれば、サイクル外の頂点を切り離しても連結のままである。
サイクル外の頂点数を x、サイクル内の頂点数を y とする。
ここまで分かれば求め方も分かるだろう。x を切り離すか、切り離さないかで場合分けする。
(1) x を切り離すとき
x の切り離し方が 2x -1 通り、y の切り離し方が 2y -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 にしては難しくない…?