LeetCode //C - 207. Course Schedule

207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Example 2:

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.

From: LeetCode
Link: 207. Course Schedule

Solution:

Ideas：

1. Graph Representation:

Each course is represented as a node in a directed graph.
Each prerequisite is represented as a directed edge from course a to course b indicating that course b must be taken before course a.

2. Cycle Detection:

For each node (course), perform a DFS to explore its adjacent nodes (prerequisites).
If, during the DFS, we revisit a node that is still being processed (VISITING), it implies that a cycle exists in the graph, and hence it is not possible to finish all courses.
If no cycles are found in the graph after exploring all nodes, it means it is possible to finish all courses.

3. DFS Traversal:

For each node, mark it as VISITING while it is being processed and explore its adjacent nodes recursively.
If a node marked as VISITING is revisited, it means a cycle is detected.
After all adjacent nodes are explored, mark the node as VISITED.

4. Adjacency List:

The graph is represented using an adjacency list, where for each node, a linked list of its adjacent nodes is maintained.

Code:

#define NOT_VISITED 0
#define VISITING 1
#define VISITED 2

typedef struct Node {
    int val;
    struct Node* next;
} Node;

typedef struct Graph {
    Node** adjList;
    int* visited;
    int numVertices;
} Graph;

Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->adjList = (Node**)malloc(numVertices * sizeof(Node*));
    graph->visited = (int*)malloc(numVertices * sizeof(int));
    graph->numVertices = numVertices;
    
    for(int i = 0; i < numVertices; i++) {
        graph->adjList[i] = NULL;
        graph->visited[i] = NOT_VISITED;
    }
    
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

bool dfs(Graph* graph, int vertex) {
    if(graph->visited[vertex] == VISITING) return false; // Cycle detected.
    if(graph->visited[vertex] == VISITED) return true;   // Already visited.
    
    graph->visited[vertex] = VISITING;
    for(Node* neighbor = graph->adjList[vertex]; neighbor != NULL; neighbor = neighbor->next)
        if(!dfs(graph, neighbor->val)) return false; // Cycle detected in the next vertex.
    
    graph->visited[vertex] = VISITED;
    return true;
}

bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize){
    Graph* graph = createGraph(numCourses);
    
    // Build adjacency list from prerequisites.
    for(int i = 0; i < prerequisitesSize; i++) 
        addEdge(graph, prerequisites[i][0], prerequisites[i][1]);
    
    // Run DFS from each vertex.
    for(int i = 0; i < numCourses; i++) 
        if(graph->visited[i] == NOT_VISITED && !dfs(graph, i)) return false;
    
    return true;
}

Navigator_Z