Articulation.c

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

#define MAX 100

// Graph representation
int arr[MAX][MAX];  // Adjacency matrix
int dfn[MAX];       // Discovery time for each node
int low[MAX];       // Lowest point reachable from each node
int num;            // Counter for discovery time
bool visited[MAX];  // Track if a vertex is visited
bool articulation[MAX]; // Track articulation points

void art(int u, int v, int n) {
    dfn[u] = low[u] = num++;
    int child = 0;
    visited[u] = true;
    
    for (int j = 0; j < n; j++) {
        if (arr[u][j] == 1) {
            if (dfn[j] == 0) { // If not visited
                child++;
                art(j, u, n);
                if (low[j] >= dfn[u]) {
                    articulation[u] = true;
                }
                low[u] = (low[u] < low[j]) ? low[u] : low[j];
            } else if (j != v) {
                low[u] = (low[u] < dfn[j]) ? low[u] : dfn[j];
            }
        }
    }
    
    // Special case for root node
    if (v == -1 && child > 1) {
        articulation[u] = true;
    }
}

void printVisited(int n) {
    printf("Articulation points: ");
    for (int i = 0; i < n; i++) {
        if (articulation[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
    
    // Print discovery times (dfn)
    printf("Discovery times: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", dfn[i] - 1); // Subtract 1 to adjust to zero-indexed vertices
    }
    printf("\n");
}

int main() {
    int n;
    printf("Enter number of vertices: ");
    scanf("%d", &n);
    
    // Initialize arrays
    for (int i = 0; i < n; i++) {
        dfn[i] = low[i] = 0;
        visited[i] = false;
        articulation[i] = false;
    }

    // Read adjacency matrix
    printf("Enter adjacency matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }

    // Start DFS from vertex 0 (can be any vertex, usually 0 for simplicity)
    num = 1;  // Set the discovery time counter to 1
    art(0, -1, n);
    
    // Output the results
    printVisited(n);
    
    return 0;
}