главная новое лучшее написать

dfs


3

Ссылка на задачу — 2115. Find All Possible Recipes from Given Supplies.
В этой задаче для эффективного решения важно не только выбрать эффективный алгоритм, но и аккуратно разложить строки по необходимым структурам данных, избежать лишних копирований и обеспечить ясную картину ownership'a за объектами.

📌 Описание задачи

💡 Идея

Используем рекурсивный DFS для проверки доступности рецептов.
Чтобы избежать повторных вычислений, применяем мемоизацию (кеширование уже проверенных результатов).

Вместо хранения графа явным образом, мы используем индексирование рецептов и проходим по их списку ингредиентов.

🔍 Детали подхода

  1. Предобработка входных данных:
    • Создаём хеш-таблицу для быстрого доступа к индексу каждого рецепта.
    • Добавляем начальные запасы в кеш доступных ингредиентов.

Читать дальше →

ответить
3

Ссылка на задачу — 3108. Minimum Cost Walk in Weighted Graph.

📌 Описание задачи

Пример

💡 Идея

Читать дальше →

1 ответ
3

Ссылка на задачу — 2467. Most Profitable Path in a Tree.

📌 Описание задачи

Дано неориентированное корневое дерево с n узлами (нумерованными от 0 до n-1).

Нужно найти максимальный чистый доход Алисы при оптимальном выборе пути.

💭 Идея

Вместо раздельного запуска BFS для поиска пути Боба и последующего прохода динамического программирования по узлам дерева, мы решим задачу одним рекурсивным DFS-проходом.

Для каждого узла будем вычислять:

Читать дальше →

ответить
3

В очередной задаче для обзора - 802. Find Eventual Safe States нам предстоит найти вершины, не попадающие в циклы графа.

📋 Описание задачи

Нужно определить безопасные вершины в ориентированном графе.

💡 Идея

Задача решается с помощью обхода графа в глубину (DFS) и вектора состояний.
Каждому узлу присваивается одно из трёх состояний:

  1. Unseen (ещё не обработан);
  2. Processing (в процессе обработки; узлы, являющиеся частью цикла, остаются в этом состоянии и после обработки);
  3. Safe (безопасный).

🔍 Детальное описание подхода

Читать дальше →

ответить