Kruskal重构树

讲解&模板
http://blog.****.net/wu_tongtong/article/details/77601523

上面那个代码是我自己yy的
这个是从网上扒拉的dalao的kruskal重构树模板
基本思路也是一样，
维护一个类似并查集的东西

其中有按秩合并和路径压缩
据说这样并查集的时间复杂度才有保证

树的记录方式：爸爸记录法（只记录父亲）
没有必要把树上的边都连起来
结点深度只要调用一个记忆化递归就好了（这个名字是我瞎起的）

大佬的模板中没有重新建点，
而直接相连，节省空间
但是这个有点难以理解

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=10010;
int n,m;
struct node{
    int x,y,v;
};
node e[N<<1];
int st[N],tot,deep[N],fa[N],f[N],size[N],z[N];

int cmp(const node &a,const node &b)
{
    return a.v<b.v;
}

int find(int a)  //路径压缩 
{
    if (fa[a]!=a) fa[a]=find(fa[a]);
    return fa[a];
}

void kruskal()
{
    sort(e+1,e+1+m,cmp);
    int i,o=0;
    for (int i=1;i<=n;i++) fa[i]=i,size[i]=1;
    for (i=1;i<=m;i++)
    {
        int f1=find(e[i].x);
        int f2=find(e[i].y);
        if (f1!=f2)
        {
            if (size[f1]>size[f2]) swap(f1,f2);  //按秩合并 
            fa[f1]=f2;  //并查集中的标志节点 
            size[f2]=max(size[f2],size[f1]+1);  //size并查集的深度 
            f[f1]=f2;   //baba 
            z[f1]=e[i].v;
        }
    }
}

int getdep(int bh)
{
    if (deep[bh]) return deep[bh];
    if (!f[bh]) return deep[bh]=1;
    return deep[bh]=getdep(f[bh])+1;
}

void print()
{
    int i,j;
    for (i=1;i<=n;i++) printf("%d's papa: %d, val: %d
",i,f[i],z[i]);
    printf("deep: ");
    for (i=1;i<=n;i++) printf("%d ",deep[i]);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v);
    kruskal();
    for (int i=1;i<=n;i++) getdep(i);
    print();
    return 0;
}