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://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;
}

原文地址:https://blog.csdn.net/navicheung/article/details/133265740

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年10月12日 07:20
python安全工具开发笔记(六)——Python爬虫BeautifulSoup模块的介绍
下一篇 2023年10月12日 08:50