Информатика · учебный маршрут
Графы, разрезы и динамические запросы
Найдите структуру связей, а затем выберите допустимое преобразование. Маленькие графы позволяют проверить каждый результат вручную.

Чему научитесь
Отличать компоненту, разделяющее ребро, путь увеличения и структуру для обновляемых сумм.
Что пригодится
- Ориентированный граф
- Вес и путь
10 тем по порядку
Читайте объяснение или сразу переходите к заданию
- Практика
Сильные компоненты: какие вершины взаимно достижимы
Компоненты сильной связности ориентированного графа: взаимная достижимость, максимальность группы и ациклический граф сжатия.
- Практика
Мост графа: удаление какого ребра разрывает связность
Мосты в неориентированном графе: удаление одного ребра, обходной путь, значения tin/low и осторожность с параллельными рёбрами.
- Практика
Точка сочленения: когда удаление вершины разделяет граф
Точки сочленения: удаление вершины со связями, особое правило корня DFS и отличие от мостового ребра.
- Практика
Паросочетание: как чередующийся путь увеличивает число пар
Увеличивающий путь в двудольном паросочетании: перестановка занятых назначений вместо жадного отказа свободной вершине.
- Практика
Остаточная сеть: зачем потоку обратные рёбра
Остаточная сеть потока: свободная пропускная способность, обратное ребро как отмена и увеличение по узкому месту пути.
- Практика
Поток и разрез: как получить проверяемую верхнюю границу
Разрез сети как доказательство оптимальности: направленные ёмкости через границу, верхняя оценка потока и совпадение с допустимым решением.
- Практика
Длиннейший путь в DAG: когда работает топологический порядок
Максимальная сумма весов в DAG: фиксированный старт, недостижимые вершины, отрицательные рёбра и обновления в топологическом порядке.
- Практика
Число путей в DAG: складываем способы, а не длины
Количество путей в ациклическом графе: сумма способов прийти к предшественникам, общий хвост и начальная единица в источнике.
- Практика
Таблица минимумов: почему перекрытие блоков допустимо не всегда
Sparse Table для минимума на отрезке: блоки длины степени двойки, безопасное перекрытие и отличие от запроса суммы.
- Практика
Дерево Фенвика: обновления и префиксные суммы по битам индекса
Дерево Фенвика для суммы:lowbit,префикс из нескольких блоков и обновление одного элемента без перестройки всех префиксов.
Как заниматься
Нужно проходить все темы подряд?
Последовательность помогает связать понятия, но можно открыть любую тему. Если задача уже знакома, начните с практики: ответ сопровождается объяснением.
Что делать, если ответ оказался неверным?
Прочитайте объяснение к ответу и сопоставьте его с разобранным примером. Найдите первый шаг, где ваше рассуждение отличается, затем попробуйте решить задание ещё раз.