Prüfer序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
namespace Prufer
{
    int n,fa[MAX],deg[MAX],p[MAX];
    inline void MakePrufer()
    {
        for(int i=1;i<=n-1;++i) ++deg[fa[i]];
        for(int i=1,j=1;i<=n-2;++i,++j)
        {
            while(deg[j]) ++j;
            p[i]=fa[j];
            while(i<=n-2&&!--deg[p[i]]&&p[i]<j) p[i+1]=fa[p[i]],++i;
        }
    }
    inline void TransPrufer()
    {
        for(int i=1;i<=n-2;++i) ++deg[p[i]];
        p[n-1]=n;
        for(int i=1,j=1;i<=n-1;++i,++j)
        {
            while(deg[j]) ++j;
            fa[j]=p[i];
            while(i<=n-2&&!--deg[p[i]]&&p[i]<j) fa[p[i]]=p[i+1],++i;
        }
    }
}