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.

解答

C++

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> indegree(numCourses, 0);
        for (const auto edge : prerequisites) {
            int a = edge[0];
            int b = edge[1];
            adj[b].push_back(a);
            indegree[a] ++;
        }
        // for (int i = 0; i < numCourses; i ++) {
        //     cout << indegree[i] << " ";
        // }
        // cout << endl;
        
        queue<int> frontier;
        for (int nodeID = 0; nodeID < numCourses; nodeID ++) {
            if (indegree[nodeID] == 0) {
                frontier.push(nodeID);
            }
        }
        vector<int> topologicalSort;
        while (not frontier.empty()) {
            int u = frontier.front();
            // cout << u << endl;
            frontier.pop();
            topologicalSort.push_back(u);
            for (int v : adj[u]) {
                indegree[v] --;
                if (indegree[v] == 0) {
                    frontier.push(v);
                }
            }
        }
        return topologicalSort.size() == numCourses;
    }
};

Jerry Wu13 July, 2023

Javascript

function canFinish(numCourses, prerequisites) {
  const graph = new Array(numCourses).fill(0).map(() => []);
  const visited = [];

  for (const [course, pre] of prerequisites) {
    graph[course].push(pre);
  }

  for (const i in graph) {
    if (!dfs(i, graph, visited)) return false;
  }

  return true;
}

function dfs(i, graph, visited) {
  if (visited[i]) return false;
  if (visited[i] === false) return true;

  visited[i] = true;
  for (const j of graph[i]) {
    if (!dfs(j, graph, visited)) return false;
  }
  visited[i] = false;

  return true;
}

參考討論區解答的
Marsgoat13 July, 2023

Reference

回到題目列表