ACM模板库

ACM模板库


prufer序列定义及性质

Prufer数列是无根树的一种数列。在组合数学中,Prufer数列由有一个对于顶点标过号的树转化来的数列,点数为n的树转化来的Prufer数列长度为n-2

对于一棵确定的无根树,对应着唯一确定的prufer序列


树$$\to$$Prufer序列

找到度为1的点中标记最小的点,删除该点,并将与之相连的点加入序列。直到剩余两个点。 上图为$$[2,2,5,6]$$ 由此可以推出,一个点在prufer序列中出现的次数为度数-1。

Prufer序列$$\to$$树

每次取出prufer序列中最前面的元素u 在点集中找到编号最小的没有在prufer序列中出现的元素v 给u,v连边然后分别删除 最后在点集中剩下两个节点,给它们连边 例如,对于prufer序列3,5,1,3 连边顺序为 2,3, 5,4, 1,5, 3,1, 3,6 (实际上与构建prufer序列时相同) 以上两种操作都可以用set维护,时间复杂度O(nlogn)

性质

页面列表

ITEM_HTML