Информатика · учебный маршрут

Графы, разрезы и динамические запросы

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

Синие фигурные скобки держат между собой оранжевый квадрат.

Чему научитесь

Отличать компоненту, разделяющее ребро, путь увеличения и структуру для обновляемых сумм.

Что пригодится

  • Ориентированный граф
  • Вес и путь

10 тем по порядку

Читайте объяснение или сразу переходите к заданию

  1. Сильные компоненты: какие вершины взаимно достижимы

    Компоненты сильной связности ориентированного графа: взаимная достижимость, максимальность группы и ациклический граф сжатия.

    Практика
  2. Мост графа: удаление какого ребра разрывает связность

    Мосты в неориентированном графе: удаление одного ребра, обходной путь, значения tin/low и осторожность с параллельными рёбрами.

    Практика
  3. Точка сочленения: когда удаление вершины разделяет граф

    Точки сочленения: удаление вершины со связями, особое правило корня DFS и отличие от мостового ребра.

    Практика
  4. Паросочетание: как чередующийся путь увеличивает число пар

    Увеличивающий путь в двудольном паросочетании: перестановка занятых назначений вместо жадного отказа свободной вершине.

    Практика
  5. Остаточная сеть: зачем потоку обратные рёбра

    Остаточная сеть потока: свободная пропускная способность, обратное ребро как отмена и увеличение по узкому месту пути.

    Практика
  6. Поток и разрез: как получить проверяемую верхнюю границу

    Разрез сети как доказательство оптимальности: направленные ёмкости через границу, верхняя оценка потока и совпадение с допустимым решением.

    Практика
  7. Длиннейший путь в DAG: когда работает топологический порядок

    Максимальная сумма весов в DAG: фиксированный старт, недостижимые вершины, отрицательные рёбра и обновления в топологическом порядке.

    Практика
  8. Число путей в DAG: складываем способы, а не длины

    Количество путей в ациклическом графе: сумма способов прийти к предшественникам, общий хвост и начальная единица в источнике.

    Практика
  9. Таблица минимумов: почему перекрытие блоков допустимо не всегда

    Sparse Table для минимума на отрезке: блоки длины степени двойки, безопасное перекрытие и отличие от запроса суммы.

    Практика
  10. Дерево Фенвика: обновления и префиксные суммы по битам индекса

    Дерево Фенвика для суммы:lowbit,префикс из нескольких блоков и обновление одного элемента без перестройки всех префиксов.

    Практика

Как заниматься

Нужно проходить все темы подряд?

Последовательность помогает связать понятия, но можно открыть любую тему. Если задача уже знакома, начните с практики: ответ сопровождается объяснением.

Что делать, если ответ оказался неверным?

Прочитайте объяснение к ответу и сопоставьте его с разобранным примером. Найдите первый шаг, где ваше рассуждение отличается, затем попробуйте решить задание ещё раз.

Все темы: Информатика