ABC054C
考えたこと
頂点数が8だから階乗で全探索してもOKだな
普段グラフは隣接リストで持つんだけど、今回は隣接行列だな
各順列について「辺があるか」をチェックすればOK
途中で辺がなければ先を探索しても無理なので深さ優先探索で枝刈りするのがいいね
公式解説OK
上記で想定解法だがbit DPでO(N^2 2^N)になるそうだ
部分集合すべてについて点Xから開始して全部をたどって点Yで終わる場合の数をもつのだな
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]