ABC232 C問題 Graph Isomorphism

問題へのリンク
### 解説この問題は, かなり読解力によって差がついた問題だと思っています. まず, 条件を整理すると, 以下の様になります.

- $P$ は $(1 , \dots , N)$ を並び替えて得られる - 任意の$1$以上$N$以下の整数$i$,$j$,について次の条件が成り立つ.

高橋君のおもちゃにおいてボール$i$とボール$j$がひもで繋がっているとき,
青木君のおもちゃにおいてボール$P_i$と$P_j$が繋がっている.

制約より, $1 \leq N \leq 8 $であることから, この問題の解法は順列全探索であることがわかります. 従って, 順列全探索により以下の様な判定を行えばよいといえます.

- 各順列$P$に対して - 1 ~ N それぞれに対して (これを $i$とする) - 高橋君のおもちゃにおいて, ボール$i$と繋がっているボールの番号全てに対して (これを$j$とする) - 青木君のおもちゃでボール$P_j$がボール$P_i$と繋がっているかを判断する - 各$i$について, 全ての条件が満たされていれば, この順列$P$は問題文の条件をクリアする.

問題文の条件をクリアした順列が$1$つでも存在すれば,`"a"`,そうでなければ `No`を出力する. 計算量は, 高橋君のおもちゃにおいて,$N$個全てのボールに対して,$N-1$個のボールが繋がっていた場合があてはまり, $O({N!} * N^{2})$程度になるといえます.今回の制約では, 十分に高速です. 以下に, 正解のソースコードの例を示します.

Rute

Rute