2021:2022 Spring - Algocourse/info GitHub Wiki

---

Занятие 12. 28 мая 2022.

• Потоки.
• Определение сети, потока.
• Дополняющая сеть, дополняющий путь.
• Теорема Форда-Фалкерсона.
• Разрез, лемма о потоке через разрез.
• Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину.
• Алгоритм масштабирования потока.
• Примеры сведения к задачам поиска потока.

Задание:

• Тренировка от СПбГУ на тему "потоки".

---

Занятие 11. 14 мая 2022.

• Декартово дерево (Дерамида, Treap).

Контест занятия

• AtCoder Beginner Contest 251

Задание:

• Реализовать декартово дерево в тренировка от СПбГУ по ДО
• Тренировка от СПбГУ

---

Занятие 10. 30 апреля 2022.

• Дерево Отрезков. Запросы на отрезках

Задание:

• Тренировка от СПбГУ

---

Занятие 9. 23 апреля 2022.

• Дерево Отрезков.

Контест занятия

• AtCoder Beginner Contest 249

Задание:

• Тренировка от СПбГУ

---

Занятие 8. 16 апреля 2022.

• Дерево Фенвика.

Контест занятия

• AtCoder Beginner Contest 248

Задание:

• Задача на дерево Фенвика
• Тренировка от СПбГУ

---

Занятие 7. 9 апреля 2022.

• Задача RMQ (range minimum query). Sparse Table

Задание:

• Задача на Sparse table

---

Занятие 6. 2 апреля 2022.

• Нахождение наименьшего общего предка. Метод двоичного подъема (LCA)

Задание:

• Набор задач.

---

Занятие 5. 19 марта 2022.

• Поиск кратчайшего пути во взвешенном графе. Алгоритм Форда-Беллмана.
• Поиск цикла отрицательного веса алгоритмом Форда-Беллмана.

Контест занятия

• AtCoder Beginner Contest 242. Виртуальный

Задание:

• Набор задач.

---

Занятие 4. 12 марта 2022.

• Поиск кратчайшего пути во взвешенном графе с неотрицательными ребрами. Алгоритм Дейкстры.

Контест занятия

• AtCoder Beginner Contest 243.

Задание:

• Набор задач 1.
• Набор задач 2.

---

Занятие 3. 26 февраля 2022.

• Поиск компонент сильной связности. Конденсация графа.
• Минимальное остовное дерево. Алгоритм Прима и алгоритм Краскала.

Контест занятия

• AtCoder Beginner Contest 241.

Задание:

• Набор тематических задач 1.
• Набор тематических задач 2.

---

Занятие 2. 19 февраля 2022.

• Алгоритм поиска мостов.
• Алгоритм поиска точек сочленения.
• Топологическая сортировка графа.

Контест занятия

• AtCoder Beginner Contest 239.

Задание:

• Задача на топологическую сортировку.
• Задача на поиск мостов.
• Подборка №1 и подборка №2 с задачами на пройденные темы графов.

---

Занятие 1. 12 февраля 2022.

• Графы. Основные понятия.
• Поиск в ширину.
• Поиск в глубину.
• Дерево обхода в глубину.
• Поиск цикла в ориентированном графе.

Задание

• Задачи на реализацию поиска в глубину (dfs).
• Задачи на реализацию поиска в ширину (bfs).
• Тренировочный контест. 12.02.2022.