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:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

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:文章来源地址https://uudwc.com/A/AAX3x

• 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;
}