这些树是同构的吗？

Question

Introduction

在这个挑战中，您的任务是编写一个程序，以确定两个给定的树是否同构。树是指一个有向无圈图，其中每个节点都正好有一个输出边，除了根，根没有。两个树是同构的，如果一棵树可以通过重命名节点来转换成另一棵树。例如，这两棵树(每条边都指向这里)

  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

输入

您的输入是两个非负整数列表，以本机格式或您的语言提供。它们按照上面指定的方式编码两棵树。您可以假设有关它们的下列条件：

1. 它们不是空的。
2. 它们的长度是一样的。
3. 每个列表L都满足所有(基于1的)索引i的L[i] < 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]

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]

Answer 1

Mathematica，48字节

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

它甚至比使用IsomorphicGraphQ的解决方案更短：

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

Answer 2

Python，83

第2行的匿名函数是我的解决方案。

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返回一个子树的规范化形式，该子树是其规范化子树的排序列表。然后，我们必须简单地检查每棵树的经典形式是否相等。