prufer编码
把无根树变成序列
6
/
5
/ \
4 2
/
3
/
1
每次看度数=1的叶子节点中删除后总数变化最小的点
删去1变化最小,输出删除1前1的父节点3
6
/
5
/ \
4 2
/
3
删去2变化最小,输出删除2前2的父节点5
6
/
5
/
4
/
3
删去3变化最小,输出4
6
/
5
/
4
删去4变化最小,输出5
6
/
5
剩下两个点后,一定删除非最大的数,最后剩下的一个点一定是输出最大的n号点 6
6
/
5
3 5 4 5
堆 O(nlogn)
prufer O(n)
从小到大枚举j(编号最小的度数=1的叶子节点),把j删掉后最多产生一个新的叶子节点
情况1:
删叶子节点后,新多出来的点k比j大,不用管,j会从小到大枚举,迟早会枚举到这个点k
情况2:
删叶子节点后,新多出来的点比j小,说明k就是当前最小叶子节点
把序列变成无根树
3 5 4 5
1 0
2 0
3 1
4 1
5 2
6 1
第1个输出的3一定是第1个最小没有出度的点1的父节点 f[1] = 3,同时3的出度-1
2 0
3 0
4 1
5 2
6 1
第2个输出的5一定是第2个最小没有出度的点2的父节点 f[2] = 5,同时5的出度-1
3 0
4 1
5 1
6 1
第3个输出的4一定是第3个最小没有出度的点3的父节点 f[3] = 4,同时4的出度-1
4 0
5 1
6 1
第4个输出的5一定是第4个最小没有出度的点4的父节点 f[4] = 5,同时5的出度-1
5 0
6 1
最后一个输出的父节点直接赋值为n f[5] = 6
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int f[N], d[N], p[N];// 每个点的父节点, 入度, prufer编码
void tree2prufer()
{
// 读入每个点的父节点
for(int i=1;i<n;i++)
{
scanf("%d",&f[i]);
d[f[i]]++;
}
for(int i=0,j=1;i<n-2;j++)// 因为最后剩下两个数的时候就不用继续删点了,所以只循环n-2次
{
while(d[j])j++;//只要j不是叶子节点,就继续从小往大搜直到找到最小的叶子节点j
p[i++] = f[j];//输出的第i个点为 j的父节点
//此时的i已经是i++后的i了,所以看j的父节点就相当于看p[i-1](上一行赋值)
//当前已经把j这个点删掉了,并且父节点编号比j小, 就把j的父节点的父节点进行输出(此时满足情况2)
while(i<n-2 && --d[p[i-1]] == 0 && p[i-1] < j)p[i++] = f[p[i-1]];
}
for(int i=0;i<n-2;i++)printf("%d ",p[i]);
}
void prufer2tree()
{
// 读入prufer序列
for (int i = 1; i <= n - 2; i ++ )
{
scanf("%d", &p[i]);
d[p[i]] ++ ;// d表示p[i]的儿子数量
}
p[n - 1] = n;// 最后只剩下两个点时,第n-1个点的父节点就是n
for (int i = 1, j = 1; i < n; i ++, j ++ )
{
while (d[j]) j ++ ;//j不是叶子节点时,就继续从小往大搜直到找到最小的叶子节点j
f[j] = p[i];//此时j是叶子节点 则f[j]就是prufer的第i个
// 删完j后 p[i]就会少一个儿子,如果p[i]儿子数量d[p[i]]==0
// 则p[i]变成新的叶子节点,并且p[i]<j的话,p[i]就是此时的最小节点,因此p[i]就是下一个被删的点,而下一个被删的点的父节点就是p[i+1]
// 所以p[i]的父节点就是p[i]的下一个节点p[i+1]
while (i < n - 1 && -- d[p[i]] == 0 && p[i] < j) f[p[i]] = p[i + 1], i ++ ;
}
for (int i = 1; i <= n - 1; i ++ ) printf("%d ", f[i]);
}
int main()
{
scanf("%d%d", &n, &m);
if (m == 1) tree2prufer();
else prufer2tree();
return 0;
}