Minimum Spanning Tree Kruskal - Second Minimum Spanning Tree - Linked List Disjoint Sets

// Implemantation Linked List represantation of Disjoint Sets
// Kruskal Implemantation
// Solves MST and Second MST
// by Iraklis Karagkiozoglou <i.kar@windowslive.com> 24/02/2011
#include <stdio.h>
#include <stdlib.h>
#define MAXNODES 2000
#define MAXEDGES 1000000
typedef struct node_t node_t;
typedef struct edge_t edge_t;

struct edge_t {
    node_t *n1, *n2;
    unsigned int cost, used;
};

struct node_t {
    node_t *parent, *root, *next, *last;
};

node_t nodes[MAXNODES];
edge_t edges[MAXEDGES];
unsigned int lasti;

void makenode(node_t *n1) {
    (*n1).last = (*n1).parent = (*n1).root = n1;
    (*n1).next = NULL;
}

void myunion(node_t *n1, node_t *n2) {
    n1 = (*n1).root;
    n2 = (*n2).root;
    (*n2).root = n1;
    (*n2).parent = (*n1).last;
    (*(*n1).last).next = n2;
    while((*n2).next!=NULL) {
        n2 = (*n2).next;
        (*n2).root = n1;
    }
}

int findset(node_t *n1, node_t *n2) {
    if((*n1).root==(*n2).root) return 1;
    else return 0;
}

int cmp(const void *a, const void *b) {
    if((*(edge_t *)a).cost>(*(edge_t *)b).cost) return 1;
    else return -1;
}

unsigned int mst_kruskal(unsigned int n, unsigned int e, unsigned int cost, unsigned int num, unsigned int j, unsigned int usede) {
    unsigned int i;
    for(i=j;i<e;i++) {
        if(num<n-1){
            if(findset(edges[i].n1,edges[i].n2)==0 && (i+1)!=usede) {
                myunion(edges[i].n1,edges[i].n2);
                if(usede==0) {
                    edges[i].used=1;
                }
                cost+=edges[i].cost;
                num++;
                lasti=i;
            }
        }
        else break;
    }
    return cost;
}

unsigned int second_kruskal(unsigned int n, unsigned int m, unsigned int cost1, unsigned int j) {
    unsigned int i, min=cost1, c, k, num;
    for(i=j+1;i>0;i--) {
        if(edges[i-1].used==1) {
            num=0;
            for(k=0;k<n;k++) makenode(&nodes[k]);
            c = mst_kruskal(n,m,0,0,0,i);
            if(min==cost1 || min>c) min =c;
        }
    }
    return min;
}

int main() {
    unsigned int n, m, i, j, k, res1, res2;
    FILE *f = fopen("christmas.in","r");
    fscanf(f,"%u %u\n",&n,&m);
    for(i=0;i<m;i++) {
        fscanf(f,"%u %u %u\n",&j,&k,&edges[i].cost);
        edges[i].n1 = &nodes[j-1];
        edges[i].n2 = &nodes[k-1];
        makenode(edges[i].n1);
        makenode(edges[i].n2);
    }
    fclose(f);
    qsort(edges,m,sizeof(edge_t),cmp);
    res1 = mst_kruskal(n,m,0,0,0,0);
    res2 = second_kruskal(n,m,res1,lasti);
    f = fopen("christmas.out","w");
    fprintf(f,"%u %u\n",res1,res2);
    return 0;
}