Disjoint Set System

graphs.c

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

typedef struct edge_s {
    int i;
    int j;
} Edge;

typedef struct graph_s {
    int num_verticies;
    int num_edges;
    Edge *edges;
} Graph;

Graph *GraphCreate(int num_verticies);
void GraphDestroy(Graph *g);
void GraphAddEdge(Graph *g, int i, int j);
int GraphComponents(Graph *g);

typedef struct djss_node_s {
    int parent;
    int size;
} DJSS_Node;

int DJSS_NumConnected(Graph *g);
int DJSS_Find(DJSS_Node *V, int i);
void DJSS_Union(DJSS_Node *V, int i, int j);

int main(int argc, char **argv) {
    Graph *g = GraphCreate(5);

    GraphAddEdge(g, 0, 1);
    // GraphAddEdge(g, 0, 2);
    // GraphAddEdge(g, 0, 3);
    GraphAddEdge(g, 0, 4);
    GraphAddEdge(g, 1, 2);
    // GraphAddEdge(g, 1, 3);
    // GraphAddEdge(g, 1, 4);
    GraphAddEdge(g, 2, 3);
    // GraphAddEdge(g, 2, 4);
    // GraphAddEdge(g, 3, 4);
    
    printf("There are %d connected components.", GraphComponents(g));

    GraphDestroy(g);

    printf("\n\n");

    return 0;
}

Graph *GraphCreate(int num_verticies) {
    Graph *g = (Graph *) malloc(sizeof(Graph));
    g->num_verticies = num_verticies;
    g->num_edges = 0;
    g->edges = NULL;
    return g;
}

void GraphDestroy(Graph *g) {
    if (g->edges != NULL) {
        free(g->edges);
        g->edges = NULL;
    }
    free(g);
}

void GraphAddEdge(Graph *g, int i, int j) {
    if (i > g->num_verticies || j > g->num_verticies)
        return;
    g->num_edges += 1;
    g->edges = (Edge *) realloc(g->edges, g->num_edges * sizeof(Edge));
    g->edges[g->num_edges - 1].i = i;
    g->edges[g->num_edges - 1].j = j;
}

int GraphComponents(Graph *g) {
    return DJSS_NumConnected(g);
}

int DJSS_Find(DJSS_Node *V, int i) {
    if (V[i].parent != i) {
        V[V[i].parent].size -= V[i].size;
        V[i].parent = DJSS_Find(V, V[i].parent);
        V[V[i].parent].size += V[i].size;
        return V[i].parent;
    } else
        return i;
}

void DJSS_Union(DJSS_Node *V, int i, int j) {
    int root_i = DJSS_Find(V, i);
    int root_j = DJSS_Find(V, j);
    if (root_i != root_j) {
        if (V[root_i].size > V[root_j].size) {
            V[root_j].parent = root_i;
            V[root_i].size += V[root_j].size;
        } else {
            V[root_i].parent = root_j;
            V[root_j].size += V[root_i].size;
        }
    }
}

int DJSS_NumConnected(Graph *g) {
    DJSS_Node *V = (DJSS_Node *) malloc(g->num_verticies * sizeof(DJSS_Node));
    int i, j, result = 0;

    for (i = 0; i < g->num_verticies; ++i) {
        V[i].parent = i;
        V[i].size = 1;
    }
    
    for (i = 0; i < g->num_edges; ++i)
        DJSS_Union(V, g->edges[i].i, g->edges[i].j);
    
    for (i = 0; i < g->num_verticies; ++i) {
        if (V[i].parent == i)
            result += 1;
    }

    free(V);
    return result;
}