Concerning Graph Part V: Connect

We present another application of DFS, which addresses the problem of connected components.

#include "graph.c"
typedef struct DFSConnectedComponentsStruct {
    bool *marked;
    int *id;
    int count;
}*DFSConnectedComponents;

void DFSConnectedComponentsSearch(DFSConnectedComponents dfscc, Graph g, int v) {
    dfscc->marked[v] = true;
    dfscc->id[v] = dfscc->count;
    int n = 0;
    int *adj = GraphAdjcency(g, v, &n);
    for (int i = 0; i < n; i++) {
        int w = adj[i];
        if (!dfscc->marked[w]) {
            DFSConnectedComponentsSearch(dfscc, g, w);
        }
    }
}

DFSConnectedComponents DFSConnectedComponentsCreate(Graph g) {
    DFSConnectedComponents dfscc = (DFSConnectedComponents)malloc(sizeof(*dfscc));
    dfscc->marked = (bool*)malloc(g->v * sizeof(bool));
    dfscc->id = (int*)malloc(g->v * sizeof(int));
    dfscc->count = 0;
    for (int i = 0; i < g->v; i++) {
        if (!dfscc->marked[i]) {
            DFSConnectedComponentsSearch(dfscc, g, i);
            dfscc->count++;
        }
    }
    return dfscc;
}

void DFSConnectedComponentsRelease(DFSConnectedComponents dfscc) {
    if (dfscc != NULL) {
        free(dfscc->marked);
        free(dfscc->id);
        free(dfscc);
    }
}

bool DFSConnectedComponentsConnected(DFSConnectedComponents dfscc, int v, int w) { return dfscc != NULL && dfscc->id[v] == dfscc->id[w]; }

int DFSConnectedComponentsId(DFSConnectedComponents dfscc, int v) { return dfscc != NULL ? dfscc->id[v] : INT_MAX; }

int DFSConnectedComponentsCount(DFSConnectedComponents dfscc) { return dfscc != NULL ? dfscc->count : INT_MIN; }