Introdução

Nesse desafio, sua tarefa é escrever um programa que decida se duas árvores são isomórficas. Uma árvore significa um gráfico acíclico direcionado em que cada nó tem exatamente uma aresta de saída, exceto a raiz, que não possui. Duas árvores são isomórficas se uma pode ser transformada na outra renomeando os nós. Por exemplo, as duas árvores (onde todas as arestas apontam para cima)

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

são facilmente vistos como isomórficos.

Codificamos uma árvore como uma lista Lde números inteiros não negativos da seguinte maneira. A raiz da árvore tem rótulo 0e também possui nós 1,2,...,length(L). Cada nó i > 0tem uma borda de saída para L[i](usando a indexação baseada em 1). Por exemplo, a lista (com os índices fornecidos sob os elementos)

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

codifica a árvore

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

Entrada

Suas entradas são duas listas de números inteiros não negativos, fornecidas no formato nativo ou no seu idioma. Eles codificam duas árvores da maneira especificada acima. Você pode assumir as seguintes condições sobre eles:

1. Eles não estão vazios.
2. Eles têm o mesmo comprimento.
3. Cada lista Latende L[i] < ia todos os índices (com base em 1) i.

Saída

Sua saída será um valor verdadeiro, se as árvores forem isomórficas, e um valor falso, se não.

Regras e pontuação

Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas. Não há restrições de tempo, mas os integrados que decidem o isomorfismo de árvore ou gráfico não são permitidos.

Casos de teste

Instâncias verdadeiras

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

Instâncias de falsidade

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

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

É ainda mais curto que a solução que usa IsomorphicGraphQ:

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

Python, 83

A função anônima na 2ª linha é a minha solução.

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)

fretorna uma forma canonizada de uma subárvore que é uma lista classificada de seus filhos canonizados. Então devemos simplesmente verificar se as formas canonizadas de cada árvore são iguais.