210. Course Schedule II
總共有 numCourses 門課程，課程標號從 0 到 numCourses - 1。你會得到一個陣列 prerequisites，其中 prerequisites[i] = [ai, bi] 表示如果你想修課程 ai，你必須先修課程 bi。
例如，對於 [0, 1] 這對數據，表示要修課程 0 你必須先修課程 1。 返回你應該按照什麼順序修完所有課程。如果有多種有效答案，返回其中任意一種。如果不可能修完所有課程，返回一個空陣列。
範例：
輸入：numCourses = 2, prerequisites = [[1,0]] 輸出：[0,1] 解釋：總共有 2 門課程。要修課程 1，你應該先完成課程 0。因此正確的課程順序是 [0,1]。
Python
from typing import List
from collections import defaultdict, deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# Create an adjacency list to represent the graph
graph = defaultdict(list)
in_degree = [0] * numCourses
# Build the graph and in-degree array
for dest, src in prerequisites:
graph[src].append(dest)
in_degree[dest] += 1
# Initialize the queue with nodes having zero in-degree
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
order = []
while queue:
course = queue.popleft()
order.append(course)
# Decrease the in-degree of neighboring nodes
for neighbor in graph[course]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# Check if the order contains all the courses
if len(order) == numCourses:
return order
else:
return []
18.23MB, 91ms
C++
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
// Create an adjacency list to represent the graph
unordered_map<int, vector<int>> graph;
vector<int> in_degree(numCourses, 0);
// Build the graph and in-degree array
for (const auto& pair : prerequisites) {
int dest = pair[0];
int src = pair[1];
graph[src].push_back(dest);
in_degree[dest]++;
}
// Initialize the queue with nodes having zero in-degree
queue<int> q;
for (int i = 0; i < numCourses; ++i) {
if (in_degree[i] == 0) {
q.push(i);
}
}
vector<int> order;
// Process the nodes in the queue
while (!q.empty()) {
int course = q.front();
q.pop();
order.push_back(course);
// Decrease the in-degree of neighboring nodes
for (int neighbor : graph[course]) {
in_degree[neighbor]--;
if (in_degree[neighbor] == 0) {
q.push(neighbor);
}
}
}
// Check if the order contains all the courses
if (order.size() == numCourses) {
return order;
} else {
return {};
}
}
};
17.72MB, 15ms
Javascript
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {number[]}
*/
var findOrder = function(numCourses, prerequisites) {
// Create an adjacency list to represent the graph
const graph = Array.from({ length: numCourses }, () => []);
const inDegree = Array(numCourses).fill(0);
// Build the graph and in-degree array
for (const [dest, src] of prerequisites) {
graph[src].push(dest);
inDegree[dest]++;
}
// Initialize the queue with nodes having zero in-degree
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) {
queue.push(i);
}
}
const order = [];
// Process the nodes in the queue
while (queue.length > 0) {
const course = queue.shift();
order.push(course);
// Decrease the in-degree of neighboring nodes
for (const neighbor of graph[course]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
// Check if the order contains all the courses
if (order.length === numCourses) {
return order;
} else {
return [];
}
};
56.02MB, 77ms
