Kruskal

#include <iostream>
#include <fstream>
#define nmaxvf 50
#define nmaxmuchii nmaxvf*(nmaxvf-1)/2
using namespace std;

struct Muchie{ int e1,e2,cost; };
Muchie G[nmaxmuchii];

int A[nmaxvf], c[nmaxvf];
int n,m;

void initializare()
{
    int i;
    ifstream fin("kruskal.in");
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>G[i].e1>>G[i].e2>>G[i].cost;
    for(i=1;i<=n;i++)
        c[i]=i;
        fin.close();
}

void afisare()
{
    int costapm=0;
    cout<<"arborele partial de cost minim este:"<<endl;
    for(int i=1;i<n;i++)
       {
            cout<<"["<<G[A[i]].e1<<","<<G[A[i]].e2<<"] cost="<<G[A[i]].cost<<endl;
    costapm+=G[A[i]].cost;
    cout<<"costul apm= "<<costapm<<endl;
       }
}

void sortm(int st, int dr)
{
    int i,j;
    Muchie x;
    if(st<dr)
    {
        x=G[st]; i=st; j=dr;
        while(i<j)
        {
            while(i<j && G[j].cost>=x.cost)
                j--;
            G[i]=G[j];
            while(i<j && G[i].cost<=x.cost)
                i++;
            G[j]=G[i];
        }
        G[i]=x;
        sortm(st,i-1);
        sortm(i+1,dr);
    }
}

int main()
{
    int i,j,min,max,nrmsel;
    initializare();
    sortm(1,m);
    nrmsel=0; //nr muchii selectate
    for(i=1;nrmsel<n-1;i++)
        if(c[G[i].e1]!=c[G[i].e2])
        //muchia i nu formeaza cicluri cu cele deja selectate
    {
        //selectez muchia i
        A[++nrmsel]=i;
        //unific componentele conexe ale extremitatilor
        if(c[G[i].e1]<c[G[i].e2])
        {
            min=c[G[i].e1];
            max=c[G[i].e2];
        }
        else
        {
            min=c[G[i].e2];
            max=c[G[i].e1];
        }
        for(j=1;j<=n;j++)
        if(c[j]==max)
            c[j]=min;
    }
    afisare();
}