prufer序列问题

解题思路

本题是无根树和 Prufer 编码相互转换的模板题，直接套模板

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int f[N]; //记录把 n 看作根节点，每个节点的父节点
int d[N]; //记录每个节点的出度
int p[N]; //记录 Prufer 编码

void tree2prufer() //无根树转化成 Prufer 编码
{
    for(int i = 1; i < n; i++)
    {
        scanf("%d", &f[i]);
        d[f[i]]++; //出度 + 1
    }

    for(int i = 0, j = 1; i < n - 2; j++)
    {
        while(d[j]) j++; //找到第一个叶节点
        p[i++] = f[j]; //输出相邻节点
        //如果删除当前最小叶节点后，它的父节点刚好是编号最小的叶节点，直接输出
        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]]++; //每个点的出度就是它在 Prufer 编码中出现的次数
    }
    p[n - 1] = n; //Prufer 序列中最后一个数一定是 n

    for(int i = 1, j = 1; i < n; i++, j++)
    {
        while(d[j]) j++; //找到第一个叶节点
        f[j] = p[i]; //j 的父节点就是 p[i]
        //如果删除 j 后，j 的父节点更好是编号最小的叶节点，继续给他配对父节点
        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(); //无根树转化成 Prufer 编码
    else prufer2tree(); //Prufer 编码转化成无根树

    return 0;
}