外观
2026-08-25
Prüfer 序列是无根树与序列的映射,可以相互转化。
每次找出所有叶子,将编号最小的叶子删去,同时输出与之相连的点,直到原图只有 222 个点。
怎么优化这个过程?我们发现,可以找出当前最小的叶子编号 jjj,在删除的过程中,如果出现比 jjj 小的叶子,就一直删,直到所有叶子比 jjj 大为止,这样做 jjj 是 O(n)O(n)O(n) 的,删除 O(n)O(n)O(n) 次,总复杂度 O(n)O(n)O(n)。
还原时,序列中出现次数即为其儿子数量,每次找到编号最小的儿子即可。
版权归属:lyrgo
许可证:署名 4.0 国际 (CC-BY-4.0)