SCC using adjacency matrix – Ashwin

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAX 100

void initializeGraph(int *graph, int num) {
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            *((graph + i * num) + j) = 0;
        }
    }
}

void addEdge(int *graph, int src, int dest, int num) {
    *((graph + src * num) + dest) = 1;
}

void print(int *graph, int num) {
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            printf(“%d “, *((graph + i * num) + j));
        }
        printf(“\n”);
    }
}

void DFS(int *graph, int src, int num, int *visited) {
    printf(” %d “, src);
    visited[src] = 1;
    for (int j = 0; j < num; j++) {
        if (*((graph + src * num) + j) == 1 && !(visited[j])) {
            DFS((int *)graph, j, num, (int *)visited);
        }
    }
}

void DFSWrapper(int *graph, int num, int *visited) {
    for (int i = 0; i < num; i++) {
        if (!visited[i]) {
            DFS((int *)graph, i, num, (int *)visited);
        }
    }
}

void printSCC(int *graph, int num) {
    int revGraph[num][num];
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            revGraph[i][j] = *((graph + j * num) + i);
        }
    }
    print((int *)revGraph, num);
}

int main() {
    int num, choice;

    printf(“Enter the number of vertices: “);
    scanf(“%d”, &num);
    int graph[num][num];
    int visited[num];
    for (int i = 0; i < num; i++) {
        visited[i] = 0;
    }
    initializeGraph((int *)graph, num);

    do {
        printf(“\nMenu:\n”);
        printf(“1. Add Edge\n”);
        printf(“2. SCC\n”);
        printf(“3. DFS\n”);
        printf(“4. Exit\n”);
        printf(“5. Print\n”);
        printf(“Enter your choice: “);
        scanf(“%d”, &choice);

        switch (choice) {
            case 1: {
                int src, dest;
                printf(“Enter source and destination vertices for the edge: “);
                scanf(“%d %d”, &src, &dest);
                addEdge((int *)graph, src, dest, num);
                printf(“Edge added successfully.\n”);
                break;
            }
            case 2:
                printSCC((int *)graph, num);
                break;
            case 3:
                DFSWrapper((int *)graph, num, (int *)visited);
                break;
            case 4:
                printf(“Exiting the program.\n”);
                break;
            case 5:
                print((int *)graph, num);
                break;
            default:
                printf(“Invalid choice. Please enter a valid option.\n”);
        }

    } while (choice != 4);

    return 0;
}