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

struct graph {
    int V; // number of vertices
    int E; // number of edges
    int **adj; // adjacency matrix
    int nC; // number of connected components
    int *cc; // componentOf array
};

// Function prototypes
void addEdge(struct graph* g, int src, int dest);
void removeEdge(struct graph* g, int src, int dest);
void DFSUtil(struct graph* g, int v, int visited[], int component);
void findConnectedComponents(struct graph* g);
struct graph* createGraph(int V, int E);
void freeGraph(struct graph* g);
void updateComponentsOnEdgeAdd(struct graph* g, int src, int dest);
void updateComponentsOnEdgeRemove(struct graph* g, int src, int dest);

int main() {
    int V = 5, E = 4;
    struct graph* g = createGraph(V, E);

    addEdge(g, 0, 1);
    addEdge(g, 1, 2);
    addEdge(g, 3, 4);

    findConnectedComponents(g);

    printf("Number of connected components: %d\n", g->nC);
    for (int i = 0; i < V; i++) {
        printf("Vertex %d is in component %d\n", i, g->cc[i]);
    }

    // Adding an edge that connects two components
    addEdge(g, 2, 3);

    printf("After adding edge 2-3:\n");
    printf("Number of connected components: %d\n", g->nC);
    for (int i = 0; i < V; i++) {
        printf("Vertex %d is in component %d\n", i, g->cc[i]);
    }

    // Removing an edge that might disconnect the graph
    removeEdge(g, 2, 3);

    printf("After removing edge 2-3:\n");
    printf("Number of connected components: %d\n", g->nC);
    for (int i = 0; i < V; i++) {
        printf("Vertex %d is in component %d\n", i, g->cc[i]);
    }

    freeGraph(g);
    return 0;
}

struct graph* createGraph(int V, int E) {
    struct graph* g = (struct graph*)malloc(sizeof(struct graph));
    g->V = V;
    g->E = E;
    g->adj = (int**)malloc(V * sizeof(int*));
    for (int i = 0; i < V; i++) {
        g->adj[i] = (int*)malloc(V * sizeof(int));
        for (int j = 0; j < V; j++) {
            g->adj[i][j] = 0;
        }
    }
    g->cc = (int*)malloc(V * sizeof(int));
    return g;
}

void addEdge(struct graph* g, int src, int dest) {
    g->adj[src][dest] = 1;
    g->adj[dest][src] = 1;

    updateComponentsOnEdgeAdd(g, src, dest);
}

void removeEdge(struct graph* g, int src, int dest) {
    g->adj[src][dest] = 0;
    g->adj[dest][src] = 0;

    updateComponentsOnEdgeRemove(g, src, dest);
}

void DFSUtil(struct graph* g, int v, int visited[], int component) {
    visited[v] = 1;
    g->cc[v] = component;

    for (int i = 0; i < g->V; i++) {
        if (g->adj[v][i] && !visited[i]) {
            DFSUtil(g, i, visited, component);
        }
    }
}

void findConnectedComponents(struct graph* g) {
    int *visited = (int*)malloc(g->V * sizeof(int));
    for (int i = 0; i < g->V; i++) {
        visited[i] = 0;
    }

    int component = 0;
    for (int v = 0; v < g->V; v++) {
        if (!visited[v]) {
            DFSUtil(g, v, visited, component);
            component++;
        }
    }

    g->nC = component;

    free(visited);
}

void updateComponentsOnEdgeAdd(struct graph* g, int src, int dest) {
    if (g->cc[src] != g->cc[dest]) {
        int oldComponent = g->cc[dest];
        int newComponent = g->cc[src];
        
        // Update all vertices of the old component to the new component
        for (int i = 0; i < g->V; i++) {
            if (g->cc[i] == oldComponent) {
                g->cc[i] = newComponent;
            }
        }
        g->nC--;
    }
}

int isPath(struct graph* g, int src, int dest, int visited[]) {
    if (src == dest) return 1;

    visited[src] = 1;

    for (int i = 0; i < g->V; i++) {
        if (g->adj[src][i] && !visited[i]) {
            if (isPath(g, i, dest, visited)) {
                return 1;
            }
        }
    }
    return 0;
}

void updateComponentsOnEdgeRemove(struct graph* g, int src, int dest) {
    int *visited = (int*)malloc(g->V * sizeof(int));
    for (int i = 0; i < g->V; i++) {
        visited[i] = 0;
    }

    if (!isPath(g, src, dest, visited)) {
        g->nC++;

        // Reassign components for one part
        int newComponent = g->nC - 1;
        DFSUtil(g, src, visited, newComponent);
    }

    free(visited);
}

void freeGraph(struct graph* g) {
    for (int i = 0; i < g->V; i++) {
        free(g->adj[i]);
    }
    free(g->adj);
    free(g->cc);
    free(g);
}