210. Course Schedule II
Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан mảng prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
НаVí dụ, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
return порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, return любой из них. Если невозможно завершить все курсы, return пустой mảng.
Ví dụ:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Giải thích: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].
C# lời giải
đã khớp/gốcpublic 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++ lời giải
bản nháp tự động, xem lại trước khi gửi#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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcfrom 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 lời giải
đã khớp/gốcpackage 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️⃣
Инициализация и построение đồ thịа:
Инициализируйте стек S, который будет содержать топологически sorted порядок курсов в нашем đồ thịе.
Постройте список смежности, используя пары ребер, указанные на Đầu vàoе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает edge вида b ➔ a. Учтите это при реализации Thuật toánа.
2️⃣
Запуск поиска в глубину (DFS):
Для каждого узла в нашем đồ thịе выполните Depth-first search (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем Depth-first search для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.
3️⃣
Обработка узлов и возвращение результата:
После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке.
После обработки всех узлов просто return узлы в порядке их присутствия в стеке от вершины до основания.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.