prufer编码 - AcWing

Processing math: 100%

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

prufer编码

作者：

清风qwq , 2023-09-12 15:47:50 , 所有人可见 , 阅读 175

4

$\LARGE{prufer编码}$

对于一个无根树，对它进行 $n-2$ 此操作：

找到度数最少的点中编号最小的点 $u$
找到点 $u$ 唯一连向的点 $v$ 并将其加入编码
从树上删除点 $u$

于是得到一个长度为 $n - 2$ 的序列

任何一棵树都唯一对应一个序列，且任何序列都唯一对应一颗无根树

所以 $n$ 个点的本质不同的无根树共有 $n^{n-2}$ 个

0 评论

1024

x