210. Course Schedule II
leetcode medium
Task
Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.
Пример:
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# solution
matched/originalpublic 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++ solution
auto-draft, review before submit#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 solution
matched/originalclass 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 solution
matched/originalclass 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 solution
matched/originalfrom 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 solution
matched/originalpackage 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{}
}
}Explanation
Algorithm
1️⃣
Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.
2️⃣
Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.
3️⃣
Обработка узлов и возвращение результата:
После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке.
После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания.
😎