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