The attempt to solve the fourth part of the problem set Tideman https://cs50.harvard.edu/x/2023/psets/3/tideman/ to lock pairs in matrix locked.

result.txt

➜  tideman_test ./tideman_test
Locking pair 0 with the result 3:0

	0	    1	    2	    3
0	false	false	false	false
1	false	false	false	false
2	false	false	false	false
3	true	false	false	false

Locking pair 1 with the result 0:1

	0	    1	    2	    3
0	false	true	false	false
1	false	false	false	false
2	false	false	false	false
3	true	false	false	false

Locking pair 2 with the result 1:2

	0	    1	    2	    3
0	false	true	false	false
1	false	false	true	false
2	false	false	false	false
3	true	false	false	false

There is a cycle: 0 -> 2 -> 1 -> 0
Pair 3 with the result 2:0 creates a cycle and couldn't be locked

	0	    1	    2	    3
0	false	true	false	false
1	false	false	true	false
2	false	false	false	false
3	true	false	false	false

Locking pair 4 with the result 3:1

	0	    1	    2	    3
0	false	true	false	false
1	false	false	true	false
2	false	false	false	false
3	true	true	false	false

There is a cycle: 0 -> 1 -> 0
Pair 5 with the result 1:0 creates a cycle and couldn't be locked

	0	    1	    2	    3
0	false	true	false	false
1	false	false	true	false
2	false	false	false	false
3	true	true	false	false

There is a cycle: 1 -> 2 -> 1
Pair 6 with the result 2:1 creates a cycle and couldn't be locked

	0	    1	    2	    3
0	false	true	false	false
1	false	false	true	false
2	false	false	false	false
3	true	true	false	false

tideman_test.c

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

#define MAX_NODES 7

int const nodes = 4;
int const pairs = 7;

int cycled = 0;

struct Edge 
{
    int source; 
    int destination;
};

struct Edge graph[MAX_NODES];
bool visited[MAX_NODES];
bool locked[MAX_NODES][MAX_NODES];
void print_lock(void);
void lock_pairs(void);
bool has_cycle(int source, int destination);
bool dfs(int source, int destination, int original);

int main() {

    // Mock the graph edges
    graph[0].source = 3;
    graph[0].destination = 0;

    graph[1].source = 0;
    graph[1].destination = 1;

    graph[2].source = 1;
    graph[2].destination = 2;

    graph[3].source = 2;
    graph[3].destination = 0;

    graph[4].source = 3;
    graph[4].destination = 1;

    graph[5].source = 1;
    graph[5].destination = 0;

    graph[6].source = 2;
    graph[6].destination = 1;

    lock_pairs();

    return 0;
}

/*
The lock_pairs() function iterates through each edge in the graph array and calls 
has_cycle to determine whether the edge should be locked or not. If it creates 
a cycle, the function prints a message indicating that the edge 
could not be locked.
*/
void lock_pairs(void) 
{
    // Reset the locked array.
    for (int i = 0; i < nodes; i++) 
    {
        for (int j = 0; j < nodes; j++) 
        {
            locked[i][j] = false;
        }
    }

    // Evaluate each pair in the graph.
    for (int i = 0; i < pairs; i++)
    {
        // If the pair does not create a cycle, lock it and print a message.
        if (!has_cycle(graph[i].source, graph[i].destination))
        {
            printf("Locking pair %i with the result %i:%i\n", i, graph[i].source, graph[i].destination);
            locked[graph[i].source][graph[i].destination] = true;
        }
        // If the pair creates a cycle, print a message indicating that it couldn't be locked.
        else
        {
            printf("Pair %i with the result %i:%i creates a cycle and couldn't be locked\n", 
                i, graph[i].source, graph[i].destination);
        }

        // Print the current state of the locked array.
        print_lock();
    }
}

/*
The has_cycle() function checks if an edge between source and destination would 
create a cycle in the graph. It does this by temporarily locking the edge, 
running a DFS from source to destination, and then unlocking the edge. If 
a cycle is detected, it returns true, otherwise false.
*/
bool has_cycle(int source, int destination)
{
    // Temporarily lock the edge between source and destination.
    locked[source][destination] = true;

    // Reset the visited array.
    for (int i = 0; i < nodes; i++) 
    {
        visited[i] = false;
    }

    // Check if there is a cycle from source to destination.
    bool result = dfs(source, destination, source);

    // Unlock the edge.
    locked[source][destination] = false;

    // Return true if there is a cycle; otherwise, return false.
    return result;
}

/* 
The dfs() function performs a DFS traversal of the graph from the source node to 
the destination node, while avoiding previously visited nodes. It also checks 
if there exists a path from the destination node back to the source node, 
thus detecting cycles.
*/
bool dfs(int source, int destination, int original)
{
    // If we have reached the destination, return true.
    if (visited[destination]) 
    {
        // Keep track of the first visited node in the cycle 
        cycled = destination;
        // Print out the cycled path
        printf("There is a cycle: %i -> ", destination);

        return true;
    }

    // Mark the current node as visited and check its adjacent nodes.
    visited[destination] = true;
    for (int i = 0; i < nodes; i++) 
    {
        // If the destination node is locked to node i and a path 
        // from i to source node exists, return true (i.e., a cycle exists).
        if (locked[destination][i] && dfs(source, i, original)) 
        {
            // Print out the cycled path
            if (destination != cycled)
            {
                printf("%i -> ", destination);
            }
            else
            {
                printf("%i\n", destination);
            }
            return true;
        }
    }

    // No cycle found in this path.
    return false;
}

/* The print_lock() function prints out the matrix of locked 2D array */
void print_lock(void)
{
    printf("\n\t");
    for (int i = 0; i < nodes; i++)
    {
        printf("%i\t", i);
    }
    printf("\n");
    for (int i = 0; i < nodes; i++)
    {
        printf("%i\t", i);
        for (int j = 0; j < nodes; j++)
        {
            printf("%s\t", locked[i][j] ? "true" : "false");
        }
        printf("\n");
    }
    printf("\n");
}