Вступление

В этой задаче ваша задача - написать программу, которая решает, являются ли два заданных дерева изоморфными. Дерево означает ориентированный ациклический граф, в котором каждый узел имеет ровно одно исходящее ребро, кроме корня, у которого его нет. Два дерева изоморфны, если одно можно преобразовать в другое путем переименования узлов. Например, два дерева (где каждое ребро направлено вверх)

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

легко увидеть, чтобы быть изоморфным.

Мы кодируем дерево как список Lнеотрицательных целых чисел следующим образом. Корень дерева имеет метку 0, а также имеет узлы 1,2,...,length(L). Каждый узел i > 0имеет исходящий фронт L[i](с использованием индексации на основе 1). Например, список (с индексами, указанными под элементами)

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

кодирует дерево

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

вход

Ваши входные данные представляют собой два списка неотрицательных целых чисел, приведенных в собственном формате или на вашем языке. Они кодируют два дерева в порядке, указанном выше. Вы можете принять следующие условия о них:

Они не пусты.
Они имеют одинаковую длину.
Каждый список Lудовлетворяет L[i] < iвсем (основанным на 1) индексам i.

Выход

Ваш вывод должен быть истинным значением, если деревья изоморфны, и ложным значением, если нет.

Правила и оценки

Вы можете написать либо полную программу, либо функцию. Побеждает меньшее количество байтов, и стандартные лазейки запрещены. Нет никаких временных ограничений, но встроенные модули, которые определяют изоморфизм дерева или графа, запрещены.

Контрольные примеры

Правдивые случаи

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

Ложные случаи

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

code-golf array-manipulation graph-theory decision-problem Zgarb
источник

1

Связанный: Математик утверждает, что прорыв в теории сложности

Цифровая Травма

@DigitalTrauma Dangit, вы сделали OP запретить встроенные функции ... У меня было 60-байтовое решение Mma ...

LegionMammal978

2

Mathematica, 48 байтов

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

Это даже короче, чем решение, которое использует IsomorphicGraphQ:

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

alephalpha
источник

6

Python, 83

Анонимная функция во второй строке - мое решение.

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)

fвозвращает канонизированную форму поддерева, представляющего собой отсортированный список его канонизированных потомков. Тогда мы должны просто проверить, равны ли канонизированные формы каждого дерева.

картонная коробка
источник

Являются ли эти деревья изоморфными?