木の同型判定
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
2 つの木 T_1 , T_2 とその頂点集合 V_1 = {1, ... , N_1}, V_2 = {1, ... , N_2}, 辺集合 E1 = {E1_1, ... , E1_{N_1-1}}, E_2 = {E2_1, ... , E2_{N_2-1}} について、E1 = E2 となる V_1 から V_2 への一対一対応の写像 f: V_1 → V_2 が存在するとき、「T_1, T_2 は同型である」といいます。
一対一対応の写像とは、V_1 を V_2 の頂点の番号に一対一で対応させる写像（一方の集合の各元に対し、他方の集合のただひとつの元を指定して結びつける対応のこと）です。
言い換えると、T_1 の頂点番号を上手く割り当てることで T_2 と一致させることができるとき、「T_1, T_2 は同型である」といえます。
例として、上のような写像は一対一対応ですが、下の写像は一対一対応ではありません。
なぜなら V_1 や V_2 のうち、選ばれていないものや、2 回以上選ばれているものが存在するためです。
写像 f において値 x が y に対応づけられたとき、このことを f(x) = y と表します。
上の写像においては f(1) = 2, f(2) = 3 ... となっています。
例として、入力例 1 の場合を考えてみましょう。T_1 , T_2 は以下の通りです。
この T_1 , T_2 では f(1) = 2, f(2) = 3, ... , f(5) = 6, f(6) = 1 といった具合に写像を考えることで以下の通り T_1 と T_2 が一致するので、T_1, T_2 は同型ということになります。
T_1 と T_2 についての情報が与えられるので、T_1 と T_2 が同型かどうかを判定してください。
- 入力される値
-
N_1
a1_1 b1_1
...
a1_{N_1-1} b1_{N_1-1}
N_2
a2_1 b2_1
...
a2_{N_2-1} b2_{N_2-1}
・1 行目には、T_1 の頂点の数 N_1 が与えられます。
・続く N_1-1 行では、T_1 の各辺の両端の頂点 a1_i , b1_i が与えられます。(1 ≦ i ≦ N_1 - 1)
・N_1+1 行目には、T_2 の頂点の数 N_1 が与えられます。
・続く N_2-1 行では、T_2 の各辺の両端の頂点 a2_i , b2_i が与えられます。(1 ≦ i ≦ N_2 - 1)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・ T_1 と T_2 が同型である場合には "YES" を、そうでない場合には "NO" を 1 行で出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N_1 , N_2 ≦ 8
・1 ≦ a1_i , b1_i ≦ N_1 (1 ≦ i ≦ N_1 - 1)
・1 ≦ a2_i , b2_i ≦ N_2 (1 ≦ i ≦ N_2 - 1)
・a1_i ≠ b1_i (1 ≦ i ≦ N_1 - 1)
・a2_i ≠ b2_i (1 ≦ i ≦ N_2 - 1)
- 入力例1
-
6
1 2
1 3
2 4
4 5
4 6
6
2 3
2 4
3 5
5 6
5 1
- 出力例1
-
YES
