Kruskal

编辑器加载中...

//------------Kruskal-------------
struct Edge
{
    int v,u;
    int weight;
}edge[M];

//----Union_Find_Set---
int ancestor[N],rank[N];
void Sinit(int n)
{
    for(int i=1;i<=n;i++)
        ancestor[i]=i,rank[i]=1;
}
int Sfind(int x)
{
    if(ancestor[x]!=x)
        return ancestor[x]=Sfind(ancestor[x]);
    return x;
}
void Sunion(int x,int y)
{
    x=ancestor[x]; y=ancestor[y];

    if(rank[x]>=rank[y])
        ancestor[y]=x,rank[x]+=rank[y];
    else
        ancestor[x]=y,rank[y]+=rank[x];
}
//----------------

int com(const void *a,const void *b)
{
    return (*(Edge*)a).weight-(*(Edge*)b).weight;
}
int Kruskal(int n,int m)
{
    int i,cnt=0,finalcost=0;

    qsort(edge,m,sizeof(edge),com);

    for(i=0;i<m;i++)
    {
        if(Sfind(edge[i].v)!=Sfind(edge[i].u))
        {
            finalcost+=edge[i].weight;
            if(++cnt==n-1)    return finalcost;
            Sunion(x,y);
        }
    }

    return -1;//IMPOSSIBLE_CONNEX
}