pengantar

Dalam tantangan ini, tugas Anda adalah menulis sebuah program yang memutuskan apakah dua pohon yang diberikan adalah isomorfik. Pohon berarti grafik asiklik terarah di mana setiap node memiliki tepat satu tepi keluar, kecuali root, yang tidak memiliki satu pun. Dua pohon isomorfis jika satu dapat ditransformasikan menjadi yang lain dengan mengganti nama node. Sebagai contoh, dua pohon (di mana setiap ujung menunjuk ke atas)

  0       0
 /|\     /|\
1 3 4   1 2 5
|\       /|
2 5     3 4

mudah terlihat isomorfik.

Kami menyandikan pohon sebagai daftar Lbilangan bulat non-negatif dengan cara berikut. Akar pohon memiliki label 0, dan juga memiliki node 1,2,...,length(L). Setiap node i > 0memiliki tepi keluar ke L[i](menggunakan pengindeksan berbasis 1). Misalnya, daftar (dengan indeks diberikan di bawah elemen)

[0,0,1,3,2,2,5,0]
 1 2 3 4 5 6 7 8

mengkodekan pohon

  0
 /|\
1 2 8
| |\
3 5 6
| |
4 7

Memasukkan

Input Anda adalah dua daftar bilangan bulat tidak negatif, yang diberikan dalam format asli atau bahasa Anda. Mereka menyandikan dua pohon dengan cara yang ditentukan di atas. Anda dapat mengasumsikan kondisi berikut tentang mereka:

1. Mereka tidak kosong.
2. Mereka memiliki panjang yang sama.
3. Setiap daftar Lmemenuhi L[i] < isemua indeks (berbasis 1) i.

Keluaran

Keluaran Anda akan menjadi nilai kebenaran jika pohonnya isomorfik, dan nilai palsu jika tidak.

Aturan dan penilaian

Anda dapat menulis program lengkap atau fungsi. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Tidak ada batasan waktu, tetapi bawaan yang memutuskan pohon atau grafik isomorfisme dilarang.

Uji kasus

Contoh yang benar

[0] [0]
[0,1,2,1] [0,1,1,3]
[0,1,1,3,3] [0,1,2,2,1]
[0,1,0,1,2,3,3,0] [0,0,2,1,0,4,2,1]
[0,1,2,3,1,2,3,0,8] [0,1,0,3,3,4,4,7,7]

Contoh palsu

[0,0] [0,1]
[0,1,2,0,3,3,4] [0,1,2,3,0,4,3]
[0,1,0,1,2,3,3,0] [0,0,2,1,0,5,2,1]
[0,1,1,0,1,3,2,1,5] [0,1,0,3,3,3,2,5,2]
[0,1,2,3,1,2,3,0,8] [0,1,0,1,4,4,5,6,6]
[0,1,0,2,0,3,0,4,0,5] [0,0,2,1,0,3,4,0,0,9]

Mathematica, 48 byte

SameQ@@(Sort//@(0(0//.PositionIndex@#))&/@{##})&

Ini bahkan lebih pendek daripada solusi yang menggunakan IsomorphicGraphQ:

IsomorphicGraphQ@@(Graph@*MapIndexed[#->Tr@#2&]/@{##})&

Python, 83

Fungsi anonim pada baris ke-2 adalah solusi saya.

f=lambda l,i=0:sorted(f(l,j+1)for j,e in enumerate(l)if e==i)
lambda a,b:f(a)==f(b)

fmengembalikan bentuk subtree yang dikanonkan yang merupakan daftar anak-anak yang dikanonkan. Maka kita harus memeriksa apakah bentuk kanonisasi setiap pohon sama.