Следующая задача для разбора - 1462. Course Schedule IV
✨ Описание задачи
У нас есть numCourses курсов, пронумерованных от 0 до numCourses - 1.
Даны:
- Массив
prerequisites, где prerequisites[i] = [a, b] указывает, что курс a необходимо пройти перед курсом b.
- Массив запросов queries, где
queries[j] = [u, v] спрашивает: является ли курс u предшественником курса v.
Нужно вернуть массив булевых значений, где для каждого запроса ответ — true, если курс u является прямым или косвенным предшественником курса v; или false, если нет.
💡 Идея
Представим зависимости курсов в виде графа, где вершины — это курсы, а ребра указывают на зависимости между ними. Наша цель — определить, существует ли путь между двумя вершинами графа. Для этого можно использовать алгоритм Флойда-Уоршелла, чтобы вычислить транзитивное замыкание графа.
🛠️ Подробности подхода
- Инициализация матрицы зависимостей: Создаем булевую матрицу
n x n, где dep_matrix[i][j] обозначает, что курс i является предшественником курса j.
- Заполнение прямых зависимостей: На основе массива
prerequisites отмечаем прямые зависимости в матрице.
- Алгоритм Флойда-Уоршелла: Используем тройной цикл для проверки всех возможных путей через промежуточные вершины (курсы). Если
dep_matrix[i][k] и dep_matrix[k][j] выполнены, то и dep_matrix[i][j] также становится true.
- Обработка запросов: Для каждого запроса проверяем значение в матрице
dep_matrix[u][v].
📊 Асимптотика
- Временная сложность:
- Инициализация матрицы:
O(N²)
- Флойд-Уоршелл:
O(N³) из-за тройного цикла.
- Обработка запросов:
O(Q), где Q — количество запросов.
- Итог:
O(N³+Q)
- Пространственная сложность:
O(N²) для матрицы зависимостей.
📄 Код
impl Solution {
pub fn check_if_prerequisite(num_courses: i32, prerequisites: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<bool> {
// Convert num_courses to usize for indexing
let num_courses = num_courses as usize;
// Step 1: Initialize the dependency matrix
let mut dep_matrix = vec![vec![false; num_courses]; num_courses];
// Step 2: Fill the direct prerequisites
for prereq in prerequisites {
let from = prereq[0] as usize;
let to = prereq[1] as usize;
dep_matrix[from][to] = true;
}
// Step 3: Compute the transitive closure using Floyd-Warshall Algorithm
for k in 0..num_courses { // Intermediate node
for i in 0..num_courses { // Start node
for j in 0..num_courses { // End node
if dep_matrix[i][k] && dep_matrix[k][j] {
dep_matrix[i][j] = true;
}
}
}
}
// Step 4: Answer the queries
queries
.into_iter()
.map(|query| dep_matrix[query[0] as usize][query[1] as usize])
.collect()
}
}
Tags: #rust #algorithms #graph