MST Kruskal

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

#define new_list_node() (malloc(sizeof(listnode)))

typedef struct _edge {
    int from;
    int to;
    int weight;
    bool is_in_mst;
} edge;

typedef struct _node {
    int label;
} node;

typedef struct _Lnode {
    node elem;
    int index;
    struct _Lnode *rappr;
    struct _Lnode *next;
} listnode;
/* Crea una nuova lista contenente il nodo passato come primo parametro */
listnode* make_set(node, listnode**);
/* Restituisce il rappresentante dell'insieme (lista) dove compare il nodo passato come terzo parametro */
listnode* find_set(listnode**, int, int);
/* Appende la lista puntata dal primo parametro in fondo alla lista puntata dal secondo e sistema i rappresentanti */
void union_set(listnode**, listnode**, listnode*, listnode*);
/* Funzioni per qsort() */
int compare_edges_lexic(const void *i, const void *j);
int compare_edges(const void *i, const void *j);

int main(void) {
    FILE *fin, *fout;
    int i;
    int from, to, weight;

    int n, m; // n = #nodi, m = #archi
    int total_weight; // Peso del MST
    edge* edges; // Array degli archi
    node* vertices; // Array dei vertici
    listnode** set; // Array di puntatori a liste (sarebbero gli insiemi disgiunti)
    listnode** tail; // Array di puntatori alla coda delle liste

    fin = fopen("input.txt","r");
    fout = fopen("output.txt","w");

    assert(fin != NULL && fout != NULL);

    assert(2 == fscanf(fin, "%i %i", &n, &m));

    vertices = malloc(n * sizeof *vertices);
    edges = malloc(2 * m * sizeof *edges); // 2m, undirected graph
    set = malloc(n * sizeof *set); // Disjoint-set
    tail = malloc(n * sizeof *tail); // Puntatori alle code delle liste
    assert(vertices != NULL && edges != NULL && set != NULL && tail != NULL);
    for(i=0;i<n;i++)
        vertices[i].label = -1;

    for(i=0;i<m;i++) {
        assert(3 == fscanf(fin, "%i %i %i", &from, &to, &weight));
        edges[i].from = from;
        edges[i].to = to;
        edges[i].weight = weight;
        edges[i].is_in_mst = false;
        /* Arco contrario, perché è non orientato */
        edges[2*m-i-1].from = to;
        edges[2*m-i-1].to = from;
        edges[2*m-i-1].weight = weight;
        edges[2*m-i-1].is_in_mst = false;
        /* Aggiungo il vertice, se non c'è già */
        if(vertices[from-1].label == -1)
            vertices[from-1].label = from;
        if(vertices[to-1].label == -1)
            vertices[to-1].label = to;
    }

    /* ALGORITMO DI KRUSKAL */

    for(i=0;i<n;i++) {
        // MAKE-SET(v)
        set[i] = make_set(vertices[i], &tail[i]); // Imposto anche la coda
    }

    qsort(edges, 2*m, sizeof(edge), compare_edges); // Ordino gli archi per peso crescente
    total_weight = 0;

    for(i=0;i<2*m;i+=2) {
        listnode *rappr_u = find_set(set, n, edges[i].from), *rappr_v = find_set(set, n, edges[i].to);
        if(rappr_u != rappr_v) { // Se sono in due alberi diversi
            edges[i].is_in_mst = true; // Prendo l'arco
            total_weight += edges[i].weight;
            union_set(set, tail, rappr_u, rappr_v); // Unisco i due alberi in un unico albero
        }

    }

    fprintf(fout, "%i\n", total_weight);
    qsort(edges, 2*m, sizeof(edge), compare_edges_lexic); // Ordino gli archi in ordine lessicografico
    for(i=0;i<2*m;i++)
        if(edges[i].is_in_mst)
            fprintf(fout, "%i %i\n", edges[i].from, edges[i].to);

    /* CLEANUP */
    fclose(fin);
    fclose(fout);
    free(vertices);
    free(edges);
    for(i=0;i<n;i++) {
        listnode *s = set[i];
        while(s != NULL) {
            listnode *tmp = s;
            s = s->next;
            free(tmp);
        }
    }
    free(set);
    free(tail);

    return 0;
}

listnode* make_set(node v, listnode** tail) {
    listnode *new = new_list_node();
    new->elem = v;
    new->rappr = new;
    new->index = v.label-1;
    new->next = NULL;

    *tail = new;
    return new;
}

listnode* find_set(listnode** set, int n, int label) {
    int i;
    // NAIF
    for(i=0;i<n;i++) { // Scorro tutti i set
        listnode *curr = set[i];
        while(curr != NULL) { // Scorro tutte le liste di tutti i set
            if(curr->elem.label == label) { // Se lo trovo..
                                            //printf("Ho trovato il rappr di %i che è %i\n",label,curr->rappr->elem.label);
                                            /* aspetta(); */
                return curr->rappr; // Restituisco il rappresentante dell'insieme
            }
            curr = curr->next;
        }
    }
    return NULL;
}

// Appende la lista di U in fondo alla lista di V
void union_set(listnode** set, listnode** tail, listnode* u, listnode* v) {
    tail[v->elem.label-1]->next = u;
    u->rappr = set[v->elem.label-1];
    /* Sistemo tutti i rappresentanti di u */
    listnode* tmp = u->next;
    while(tmp != NULL) {
        tmp->rappr = set[v->elem.label-1];
        tmp = tmp->next;
    }

    set[u->elem.label-1] = NULL;
    tail[v->elem.label-1] = tail[u->elem.label-1];
}

/* Relazione di ordinamento lessicografico degli archi */
int compare_edges_lexic(const void *i, const void *j) {
    int diff_from = ((edge *) (i))->from - ((edge *) (j))->from;
    if(diff_from == 0)
        return ((edge *) (i))->to - ((edge *) (j))->to;
    return diff_from;
}

/* Relazione di ordinamento in base al peso degli archi */
int compare_edges(const void *i, const void *j) {
    int diff_weight = ((edge *) (i))->weight - ((edge *) (j))->weight;
    if(diff_weight == 0)
        return compare_edges_lexic(i, j);
    return diff_weight;
}