Wprowadzenie

W tym wyzwaniu Twoim zadaniem jest napisanie programu, który decyduje, czy dwa dane drzewa są izomorficzne. Drzewo oznacza ukierunkowany wykres acykliczny, w którym każdy węzeł ma dokładnie jedną krawędź wychodzącą, z wyjątkiem korzenia, który go nie ma. Dwa drzewa są izomorficzne, jeśli jedno można przekształcić w drugie, zmieniając nazwę węzłów. Na przykład dwa drzewa (gdzie każda krawędź jest skierowana w górę)

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

są łatwo widoczne jako izomorficzne.

Drzewo kodujemy jako listę Lnieujemnych liczb całkowitych w następujący sposób. Korzeń drzewa ma etykietę 0, a także węzły 1,2,...,length(L). Każdy węzeł i > 0ma krawędź wychodzącą do L[i](za pomocą indeksowania 1). Na przykład lista (z indeksami podanymi pod elementami)

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

koduje drzewo

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

Wkład

Twoje dane wejściowe to dwie listy nieujemnych liczb całkowitych, podane w natywnym formacie lub języku. Kodują dwa drzewa w sposób określony powyżej. Możesz założyć o nich następujące warunki:

1. Nie są puste.
2. Mają tę samą długość.
3. Każda lista Lspełnia L[i] < iwszystkie indeksy (1) i.

Wydajność

Twój wynik powinien być prawdziwą wartością, jeśli drzewa są izomorficzne, a wartością fałszowania, jeśli nie.

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Nie ma ograniczeń czasowych, ale wbudowane elementy decydujące o izomorfizmie drzewa lub wykresu są niedozwolone.

Przypadki testowe

Prawdziwe przypadki

[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]

Instancje Falsy

[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 bajtów

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

Jest nawet krótszy niż rozwiązanie, które wykorzystuje IsomorphicGraphQ:

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

Python, 83

Anonimowa funkcja w 2. linii jest moim rozwiązaniem.

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)

fzwraca kanonizowaną formę poddrzewa, które jest posortowaną listą jego kanonizowanych potomków. Następnie musimy po prostu sprawdzić, czy kanonizowane formy każdego drzewa są równe.