207. Course Schedule
總共有 numCourses 門課程，課程標號從 0 到 numCourses - 1。你會得到一個陣列 prerequisites，其中 prerequisites[i] = [ai, bi] 表示如果你想修課程 ai，你必須先修課程 bi。
例如，對於 [0, 1] 這對數據，表示要修課程 0 你必須先修課程 1。
如果你能完成所有課程，返回 true。否則，返回 false。
範例：
輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：true
解釋：總共有 2 門課程。要修課程 1，你應該先完成課程 0。因此這是可行的。
Python
from typing import List
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# Create an adjacency list to represent the graph
graph = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
graph[course].append(prereq)
# Track visited nodes to detect cycles
visited = [0] * numCourses
# Define a helper function to perform DFS
def dfs(course):
if visited[course] == -1: # This node is being visited, so we have a cycle
return False
if visited[course] == 1: # This node has been visited, so no cycle from this node
return True
# Mark the node as being visited
visited[course] = -1
# Visit all the prerequisites
for prereq in graph[course]:
if not dfs(prereq):
return False
# Mark the node as fully visited
visited[course] = 1
return True
# Perform DFS for each course
for course in range(numCourses):
if not dfs(course):
return False
return True
18.20MB, 86ms
C++
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
// Create an adjacency list to represent the graph
vector<vector<int>> graph(numCourses);
for (const auto& pair : prerequisites) {
graph[pair[1]].push_back(pair[0]);
}
// Track visited nodes to detect cycles
vector<int> visited(numCourses, 0);
// Define a helper function to perform DFS
function<bool(int)> dfs = [&](int course) {
if (visited[course] == -1) { // This node is being visited, so we have a cycle
return false;
}
if (visited[course] == 1) { // This node has been visited, so no cycle from this node
return true;
}
// Mark the node as being visited
visited[course] = -1;
// Visit all the prerequisites
for (int prereq : graph[course]) {
if (!dfs(prereq)) {
return false;
}
}
// Mark the node as fully visited
visited[course] = 1;
return true;
};
// Perform DFS for each course
for (int course = 0; course < numCourses; ++course) {
if (!dfs(course)) {
return false;
}
}
return true;
}
};
17.42MB, 15ms
Javascipt
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
var canFinish = function(numCourses, prerequisites) {
// Create an adjacency list to represent the graph
const graph = Array.from({ length: numCourses }, () => []);
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
}
// Track visited nodes to detect cycles
const visited = new Array(numCourses).fill(0); // 0 = not visited, -1 = visiting, 1 = visited
// Define a helper function to perform DFS
const dfs = (course) => {
if (visited[course] === -1) { // This node is being visited, so we have a cycle
return false;
}
if (visited[course] === 1) { // This node has been visited, so no cycle from this node
return true;
}
// Mark the node as being visited
visited[course] = -1;
// Visit all the prerequisites
for (const prereq of graph[course]) {
if (!dfs(prereq)) {
return false;
}
}
// Mark the node as fully visited
visited[course] = 1;
return true;
};
// Perform DFS for each course
for (let course = 0; course < numCourses; course++) {
if (!dfs(course)) {
return false;
}
}
return true;
};
55.20MB, 75ms
