Articulation Points and Bridges in C

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

#define MAX_VERTICES 100

// Structure to represent a node in the adjacency list
struct Node {
    int vertex;
    struct Node* next;
};

// Function to create a new adjacency list node
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Function to add an edge to the adjacency list
void addEdge(struct Node* adjacencyList[], int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = adjacencyList[src];
    adjacencyList[src] = newNode;

    newNode = createNode(src);
    newNode->next = adjacencyList[dest];
    adjacencyList[dest] = newNode;
}

// Function to perform a depth-first search and find articulation points and bridges
void dfs(int u, int parent, int discoveryTime[], int lowTime[], int visited[], int isArticulation[], struct Node* adjacencyList[]) {
    static int time = 0;
    int children = 0;

    visited[u] = 1;
    discoveryTime[u] = lowTime[u] = ++time;

    struct Node* currentNode = adjacencyList[u];

    while (currentNode != NULL) {
        int v = currentNode->vertex;

        if (!visited[v]) {
            children++;
            dfs(v, u, discoveryTime, lowTime, visited, isArticulation, adjacencyList);

            // Update lowTime after DFS traversal of a child
            lowTime[u] = (lowTime[u] < lowTime[v]) ? lowTime[u] : lowTime[v];

            // Check for articulation points
            if (lowTime[v] >= discoveryTime[u] && parent != -1) {
                isArticulation[u] = 1;
            }

            // Check for bridges
            if (lowTime[v] > discoveryTime[u]) {
                printf("Bridge: %d-%d\n", u, v);
            }
        } else if (v != parent) {
            lowTime[u] = (lowTime[u] < discoveryTime[v]) ? lowTime[u] : discoveryTime[v];
        }

        currentNode = currentNode->next;
    }

    // Check for the root node as an articulation point
    if (parent == -1 && children > 1) {
        isArticulation[u] = 1;
    }
}

// Function to find and print articulation points in the graph
void findArticulationPoints(int numVertices, struct Node* adjacencyList[]) {
    int discoveryTime[MAX_VERTICES];
    int lowTime[MAX_VERTICES];
    int visited[MAX_VERTICES];
    int isArticulation[MAX_VERTICES];

    for (int i = 0; i < numVertices; i++) {
        visited[i] = 0;
        isArticulation[i] = 0;
    }

    for (int i = 0; i < numVertices; i++) {
        if (!visited[i]) {
            dfs(i, -1, discoveryTime, lowTime, visited, isArticulation, adjacencyList);
        }
    }

    printf("Articulation Points:\n");
    for (int i = 0; i < numVertices; i++) {
        if (isArticulation[i]) {
            printf("%d\n", i);
        }
    }
}

int main() {
    int numVertices = 5;
    struct Node* adjacencyList[MAX_VERTICES];

    for (int i = 0; i < numVertices; i++) {
        adjacencyList[i] = NULL;
    }

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

    printf("Articulation Points and Bridges in the Graph:\n");
    findArticulationPoints(numVertices, adjacencyList);

    return 0;
}