Kruskal's Algorithm for Minimum Spanning Tree

Kruskal's Algorithm is a Greedy algorithm which calculates the Minimum Spanning Tree of an undirected graph. It works as follows:
1) Sort the edges according to their weight.
2) Choose the edge with minimum weight
3) Take the next minimum edge - if it does not form a cycle with the existing edges in the MST, add it to the MST. Else, go to the next edge and repeat this step.
To check whether the next edge does not form a cycle with the existing edges, we use a Data Structure called Union-Find or Disjoint Set Data Structure. This can be implemented using arrays. To keep complexity minimum, we use Union-By-Rank and Path Compression.
Hence overall complexity of the algorithm is O(ElogE) for sorting + O(E) for the Disjoint-Set Data Structure operations = Overall O(ElogE).

#define MAXN 10000 // number of edges

struct node
{
    int x;
    int y;
    int w;
}e[MAXN];

int id[MAXN],sz[MAXN];

int root(int i)
{
    while(i!=id[i])
    {
        id[i]=id[id[i]];
        i=id[i];
    }
    return i;
}

void qunion(int p, int q)
{
    int i = root(p), j=root(q);
    if(sz[i] < sz[j]) {id[i]=j; sz[j]+=sz[i];}
    else                {id[j]=id[i]; sz[i]+=sz[j];}
}

bool fun(const node &a, const node &b)
{
    return a.w < b.w;
}

int main()
{
    int t,n,u,v,w,ans,k,adj;
    n=GI; k=0; ans=0;
    // Take input of edges, their weights and set id[i]=i, sz[i]=1 for each vertex
    REP(i,0,n)
    {
      e[k].x=GI; e[k].y=GI; e[k].w=GI;
      id[e[k].x]=e[k].x; id[e[k].y]=e[k].y; sz[e[k].x]=1; sz[e[k].y]=1;
      k++;
    }
    sort(e,e+k,fun);
    REP(i,0,k)
    {
      if(root(e[i].x)!=root(e[i].y))
      {
        qunion(e[i].x,e[i].y);
        ans+=e[i].w;
      }
    }
 printf("%d\n",ans);
 return 0;
}

Practice Problem:
BLINNET