Всего у вас есть numCourses курсов, которые нужно пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните true, если вы можете завершить все курсы. В противном случае верните false.
Пример:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
C# решение
сопоставлено/оригиналpublic class Solution {
public bool CanFinish(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses];
List<int>[] adj = new List<int>[numCourses];
for (int i = 0; i < numCourses; i++) {
adj[i] = new List<int>();
}
foreach (var prerequisite in prerequisites) {
adj[prerequisite[1]].Add(prerequisite[0]);
indegree[prerequisite[0]]++;
}
Queue<int> q = new Queue<int>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
q.Enqueue(i);
}
}
int nodesVisited = 0;
while (q.Count > 0) {
int node = q.Dequeue();
nodesVisited++;
foreach (var neighbor in adj[node]) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
q.Enqueue(neighbor);
}
}
}
return nodesVisited == numCourses;
}
}C++ решение
auto-draft, проверить перед отправкой#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:
public bool CanFinish(int numCourses, int[][] prerequisites) {
vector<int>& indegree = new int[numCourses];
List<int>[] adj = new List<int>[numCourses];
for (int i = 0; i < numCourses; i++) {
adj[i] = new List<int>();
}
foreach (var prerequisite in prerequisites) {
adj[prerequisite[1]].push_back(prerequisite[0]);
indegree[prerequisite[0]]++;
}
queue<int> q = new queue<int>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
q.Enqueue(i);
}
}
int nodesVisited = 0;
while (q.size() > 0) {
int node = q.Dequeue();
nodesVisited++;
foreach (var neighbor in adj[node]) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
q.Enqueue(neighbor);
}
}
}
return nodesVisited == numCourses;
}
}Java решение
сопоставлено/оригиналclass Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses];
List<List<Integer>> adj = new ArrayList<>(numCourses);
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
adj.get(prerequisite[1]).add(prerequisite[0]);
indegree[prerequisite[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int nodesVisited = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
nodesVisited++;
for (int neighbor : adj.get(node)) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
return nodesVisited == numCourses;
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
canFinish(numCourses, prerequisites) {
const indegree = new Array(numCourses).fill(0);
const adj = Array.from({ length: numCourses }, () => []);
for (const [a, b] of prerequisites) {
adj[b].push(a);
indegree[a]++;
}
const q = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) {
q.push(i);
}
}
let nodesVisited = 0;
while (q.length > 0) {
const node = q.shift();
nodesVisited++;
for (const neighbor of adj[node]) {
indegree[neighbor]--;
if (indegree[neighbor] === 0) {
q.push(neighbor);
}
}
}
return nodesVisited === numCourses;
}
}Python решение
сопоставлено/оригиналclass Solution:
def canFinish(self, numCourses, prerequisites):
indegree = [0] * numCourses
adj = [[] for _ in range(numCourses)]
for prerequisite in prerequisites:
adj[prerequisite[1]].append(prerequisite[0])
indegree[prerequisite[0]] += 1
queue = deque()
for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)
nodesVisited = 0
while queue:
node = queue.popleft()
nodesVisited += 1
for neighbor in adj[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return nodesVisited == numCoursesGo решение
сопоставлено/оригиналpackage main
func canFinish(numCourses int, prerequisites [][]int) bool {
indegree := make([]int, numCourses)
adj := make([][]int, numCourses)
for _, prerequisite := range prerequisites {
adj[prerequisite[1]] = append(adj[prerequisite[1]], prerequisite[0])
indegree[prerequisite[0]]++
}
queue := []int{}
for i := 0; i < numCourses; i++ {
if indegree[i] == 0 {
queue = append(queue, i)
}
}
nodesVisited := 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
nodesVisited++
for _, neighbor := range adj[node] {
indegree[neighbor]--
if indegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
return nodesVisited == numCourses
}Algorithm
1️⃣
Создайте массив indegree длины n, где indegree[x] хранит количество входящих рёбер в узел x. Создайте список смежности adj, в котором adj[x] содержит все узлы с входящим ребром от узла x, то есть соседей узла x. Создайте этот список смежности, итерируя prerequisites. Для каждого prerequisites добавьте ребро от prerequisites[1] к prerequisites[0] и увеличьте indegree prerequisites[0] на 1.
2️⃣
Инициализируйте очередь целых чисел q и начните алгоритм BFS, перемещаясь от листовых узлов к родительским узлам. Начните обход BFS, поместив все листовые узлы (indegree равное 0) в очередь. Создайте целочисленную переменную nodesVisited = 0 для подсчета количества посещенных узлов.
3️⃣
Пока очередь не пуста:
Извлеките первый узел из очереди.
Увеличьте nodesVisited на 1.
Для каждого соседа (узлы, которые имеют входящее ребро от узла) узла уменьшите indegree[neighbor] на 1, чтобы удалить ребро node -> neighbor.
Если indegree[neighbor] == 0, это означает, что neighbor ведет себя как листовой узел, поэтому добавьте neighbor в очередь.
Если количество посещенных узлов меньше общего количества узлов, то есть nodesVisited < n, верните false, так как должен быть цикл. В противном случае, если nodesVisited == numCourses, верните true. Можно сократить это до просто возвращения nodesVisited == numCourses.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.