210. Course Schedule II
Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан 배열 prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
На예제, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
return порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, return любой из них. Если невозможно завершить все курсы, return пустой 배열.
예제:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
설명: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].
C# 해법
매칭됨/원본public class Solution {
private const int WHITE = 1;
private const int GRAY = 2;
private const int BLACK = 3;
public int[] FindOrder(int numCourses, int[][] prerequisites) {
bool isPossible = true;
var color = new Dictionary<int, int>();
var adjList = new Dictionary<int, List<int>>();
var topologicalOrder = new List<int>();
for (int i = 0; i < numCourses; i++) color[i] = WHITE;
foreach (var relation in prerequisites) {
int dest = relation[0];
int src = relation[1];
if (!adjList.ContainsKey(src)) adjList[src] = new List<int>();
adjList[src].Add(dest);
}
for (int i = 0; i < numCourses && isPossible; i++) {
if (color[i] == WHITE) {
Dfs(i, color, adjList, ref isPossible, topologicalOrder);
}
}
if (isPossible) {
var order = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
order[i] = topologicalOrder[numCourses - i - 1];
}
return order;
} else {
return new int[0];
}
}
private void Dfs(int node, Dictionary<int, int> color, Dictionary<int, List<int>> adjList,
ref bool isPossible, List<int> topologicalOrder) {
if (!isPossible) return;
color[node] = GRAY;
if (adjList.ContainsKey(node)) {
foreach (int neighbor in adjList[node]) {
if (color[neighbor] == WHITE) {
Dfs(neighbor, color, adjList, ref isPossible, topologicalOrder);
} else if (color[neighbor] == GRAY) {
isPossible = false;
}
}
}
color[node] = BLACK;
topologicalOrder.Add(node);
}
}C++ 해법
자동 초안, 제출 전 검토#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private const int WHITE = 1;
private const int GRAY = 2;
private const int BLACK = 3;
public vector<int>& FindOrder(int numCourses, int[][] prerequisites) {
bool isPossible = true;
var color = new unordered_map<int, int>();
var adjList = new unordered_map<int, List<int>>();
var topologicalOrder = new List<int>();
for (int i = 0; i < numCourses; i++) color[i] = WHITE;
foreach (var relation in prerequisites) {
int dest = relation[0];
int src = relation[1];
if (!adjList.count(src)) adjList[src] = new List<int>();
adjList[src].push_back(dest);
}
for (int i = 0; i < numCourses && isPossible; i++) {
if (color[i] == WHITE) {
Dfs(i, color, adjList, ref isPossible, topologicalOrder);
}
}
if (isPossible) {
var order = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
order[i] = topologicalOrder[numCourses - i - 1];
}
return order;
} else {
return new int[0];
}
}
private void Dfs(int node, unordered_map<int, int> color, unordered_map<int, List<int>> adjList,
ref bool isPossible, List<int> topologicalOrder) {
if (!isPossible) return;
color[node] = GRAY;
if (adjList.count(node)) {
foreach (int neighbor in adjList[node]) {
if (color[neighbor] == WHITE) {
Dfs(neighbor, color, adjList, ref isPossible, topologicalOrder);
} else if (color[neighbor] == GRAY) {
isPossible = false;
}
}
}
color[node] = BLACK;
topologicalOrder.push_back(node);
}
}Java 해법
매칭됨/원본class Solution {
static int WHITE = 1;
static int GRAY = 2;
static int BLACK = 3;
boolean isPossible;
Map<Integer, Integer> color;
Map<Integer, List<Integer>> adjList;
List<Integer> topologicalOrder;
private void init(int numCourses) {
this.isPossible = true;
this.color = new HashMap<>();
this.adjList = new HashMap<>();
this.topologicalOrder = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
this.color.put(i, WHITE);
}
}
private void dfs(int node) {
if (!this.isPossible) return;
this.color.put(node, GRAY);
for (Integer neighbor : this.adjList.getOrDefault(node, new ArrayList<>())) {
if (this.color.get(neighbor) == WHITE) {
this.dfs(neighbor);
} else if (this.color.get(neighbor) == GRAY) {
this.isPossible = false;
}
}
this.color.put(node, BLACK);
this.topologicalOrder.add(node);
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
this.init(numCourses);
for (int i = 0; i < prerequisites.length; i++) {
int dest = prerequisites[i][0];
int src = prerequisites[i][1];
List<Integer> lst = adjList.getOrDefault(src, new ArrayList<>());
lst.add(dest);
adjList.put(src, lst);
}
for (int i = 0; i < numCourses; i++) {
if (this.color.get(i) == WHITE) {
this.dfs(i);
}
}
if (this.isPossible) {
int[] order = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
order[i] = this.topologicalOrder.get(numCourses - i - 1);
}
return order;
} else {
return new int[0];
}
}
}JavaScript 해법
매칭됨/원본class Solution {
constructor() {
this.WHITE = 1;
this.GRAY = 2;
this.BLACK = 3;
this.isPossible = true;
this.color = new Map();
this.adjList = new Map();
this.topologicalOrder = [];
}
findOrder(numCourses, prerequisites) {
for (let i = 0; i < numCourses; i++) {
this.color.set(i, this.WHITE);
}
for (let [dest, src] of prerequisites) {
if (!this.adjList.has(src)) {
this.adjList.set(src, []);
}
this.adjList.get(src).push(dest);
}
for (let i = 0; i < numCourses && this.isPossible; i++) {
if (this.color.get(i) === this.WHITE) {
this.dfs(i);
}
}
if (this.isPossible) {
const order = new Array(numCourses);
for (let i = 0; i < numCourses; i++) {
order[i] = this.topologicalOrder[numCourses - i - 1];
}
return order;
} else {
return [];
}
}
dfs(node) {
if (!this.isPossible) return;
this.color.set(node, this.GRAY);
if (this.adjList.has(node)) {
for (let neighbor of this.adjList.get(node)) {
if (this.color.get(neighbor) === this.WHITE) {
this.dfs(neighbor);
} else if (this.color.get(neighbor) === this.GRAY) {
this.isPossible = false;
}
}
}
this.color.set(node, this.BLACK);
this.topologicalOrder.push(node);
}
}Python 해법
매칭됨/원본from collections import defaultdict
class Solution:
WHITE = 1
GRAY = 2
BLACK = 3
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj_list = defaultdict(list)
for dest, src in prerequisites:
adj_list[src].append(dest)
topological_sorted_order = []
is_possible = True
color = {k: Solution.WHITE for k in range(numCourses)}
def dfs(node: int) -> None:
nonlocal is_possible
if not is_possible:
return
color[node] = Solution.GRAY
if node in adj_list:
for neighbor in adj_list[node]:
if color[neighbor] == Solution.WHITE:
dfs(neighbor)
elif color[neighbor] == Solution.GRAY:
is_possible = False
color[node] = Solution.BLACK
topological_sorted_order.append(node)
for vertex in range(numCourses):
if color[vertex] == Solution.WHITE:
dfs(vertex)
return topological_sorted_order[::-1] if is_possible else []Go 해법
매칭됨/원본package main
func findOrder(numCourses int, prerequisites [][]int) []int {
const (
WHITE = 1
GRAY = 2
BLACK = 3
)
isPossible := true
color := make(map[int]int)
adjList := make(map[int][]int)
var topologicalOrder []int
for i := 0; i < numCourses; i++ {
color[i] = WHITE
}
for _, relation := range prerequisites {
dest := relation[0]
src := relation[1]
adjList[src] = append(adjList[src], dest)
}
var dfs func(int)
dfs = func(node int) {
if !isPossible {
return
}
color[node] = GRAY
for _, neighbor := range adjList[node] {
if color[neighbor] == WHITE {
dfs(neighbor)
} else if color[neighbor] == GRAY {
isPossible = false
}
}
color[node] = BLACK
topologicalOrder = append(topologicalOrder, node)
}
for i := 0; i < numCourses && isPossible; i++ {
if color[i] == WHITE {
dfs(i)
}
}
if isPossible {
order := make([]int, numCourses)
for i := 0; i < numCourses; i++ {
order[i] = topologicalOrder[numCourses-i-1]
}
return order
} else {
return []int{}
}
}Algorithm
1️⃣
Инициализация и построение 그래프а:
Инициализируйте стек S, который будет содержать топологически sorted порядок курсов в нашем 그래프е.
Постройте список смежности, используя пары ребер, указанные на 입력е. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает edge вида b ➔ a. Учтите это при реализации 알고리즘а.
2️⃣
Запуск поиска в глубину (DFS):
Для каждого узла в нашем 그래프е выполните Depth-first search (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем Depth-first search для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.
3️⃣
Обработка узлов и возвращение результата:
После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке.
После обработки всех узлов просто return узлы в порядке их присутствия в стеке от вершины до основания.
😎
Vacancies for this task
활성 채용 with overlapping task tags are 표시됨.