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:
- Nie są puste.
- Mają tę samą długość.
- Każda lista
LspełniaL[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]