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

#define MAX_PROCESSES 5
#define MAX_RESOURCES 3

// Function to check if all processes can finish
bool canFinish(int process, int finish[], int need[MAX_PROCESSES][MAX_RESOURCES], int work[], int m) {
    for (int i = 0; i < m; i++) {
        if (need[process][i] > work[i])
            return false;
    }
    return true;
}

// Deadlock Detection Function
bool detectDeadlock(int processes[], int available[], int max[MAX_PROCESSES][MAX_RESOURCES], int allocation[MAX_PROCESSES][MAX_RESOURCES], int need[MAX_PROCESSES][MAX_RESOURCES], int n, int m) {
    int work[MAX_RESOURCES];
    int finish[MAX_PROCESSES] = {0};

    // Initialize work as available
    for (int i = 0; i < m; i++) {
        work[i] = available[i];
    }

    bool deadlock = false;

    for (int i = 0; i < n; i++) {
        if (!finish[i] && canFinish(i, finish, need, work, m)) {
            for (int j = 0; j < m; j++) {
                work[j] += allocation[i][j];
            }
            finish[i] = 1;
            i = -1; // Restart the process to check for others
        }
    }

    for (int i = 0; i < n; i++) {
        if (!finish[i]) {
            deadlock = true;
            printf("Process %d is in deadlock\n", i);
        }
    }

    return deadlock;
}

int main() {
    int n = MAX_PROCESSES;  // Number of processes
    int m = MAX_RESOURCES;  // Number of resources

    int processes[MAX_PROCESSES] = {0, 1, 2, 3, 4};

    // Available instances of resources
    int available[MAX_RESOURCES] = {3, 3, 2};

    // Maximum R that can be allocated to processes
    int max[MAX_PROCESSES][MAX_RESOURCES] = {
        {7, 5, 3},
        {3, 2, 2},
        {9, 0, 2},
        {2, 2, 2},
        {4, 3, 3}
    };

    // Resources allocated to processes
    int allocation[MAX_PROCESSES][MAX_RESOURCES] = {
        {0, 1, 0},
        {2, 0, 0},
        {3, 0, 2},
        {2, 1, 1},
        {0, 0, 2}
    };

    // Need of each process
    int need[MAX_PROCESSES][MAX_RESOURCES];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            need[i][j] = max[i][j] - allocation[i][j];
        }
    }

    if (detectDeadlock(processes, available, max, allocation, need, n, m)) {
        printf("System is in Deadlock.\n");
    } else {
        printf("No Deadlock Detected.\n");
    }

    return 0;
}