Продвинутые DFS и BFS

Топологическая сортировка, 0-1 BFS, мосты и точки сочленения, двудольность

IOI Prep Camp — Abbas Aliyev — апрель 2026

📄 Раздаточный материал: DFS & BFS basics (Day 1)

DFS — напоминание

vector<bool> visited;
vector<vector<int>> adj;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
}
      

BFS — напоминание

vector<int> dist(n + 1, -1);
queue<int> q;
dist[s] = 0;
q.push(s);

while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : adj[v]) {
        if (dist[u] == -1) {
            dist[u] = dist[v] + 1;
            q.push(u);
        }
    }
}
      

Сегодняшний план

Задача: порядок курсов

Правильный порядок: Матан, Программирование, Линал, Теорвер, Алгоритмы, ML

Определение

Топосорт через DFS

1. Запускаем DFS из каждой непосещённой вершины
2. Когда DFS покидает вершину (после всех потомков), добавляем её в список
3. Ответ — обратный порядок (reverse)

Код: топосорт через DFS

int n, m;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> order;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) dfs(u);
    }
    order.push_back(v); // при выходе из вершины
}

void topological_sort() {
    visited.assign(n + 1, false);
    for (int v = 1; v <= n; v++)
        if (!visited[v]) dfs(v);
    reverse(order.begin(), order.end());
}
  

⬆ Ключевая строка — order.push_back(v) при ВЫХОДЕ, не при входе

Сложность: O(V + E)

Пример: DFS топосорт

DAG: 1→2, 1→3, 2→4, 3→4, 3→5, 4→6, 5→6

А если есть цикл?

В ориентированном графе нужен другой подход — три цвета:

• ⬜ Белый (0): ещё не посещена
• 🔘 Серый (1): в процессе (в стеке DFS)
• ⬛ Чёрный (2): полностью обработана

vector<int> color; // 0 = белый, 1 = серый, 2 = чёрный
bool has_cycle = false;

void dfs(int v) {
    color[v] = 1;
    for (int u : adj[v]) {
        if (color[u] == 1) { has_cycle = true; return; }
        if (color[u] == 0) dfs(u);
    }
    color[v] = 2;
}
  

Топосорт через BFS: алгоритм Кана

1. Посчитать входящую степень (in-degree) каждой вершины
2. Добавить в очередь все вершины с in-degree = 0
3. Пока очередь не пуста: достать v, добавить в ответ, для каждого соседа u уменьшить in-degree[u]. Если стало 0 — в очередь.
4. Если обработали все n вершин — топосорт найден. Иначе — цикл!

Код: алгоритм Кана

vector<int> topological_sort_kahn(int n, vector<vector<int>>& adj) {
    vector<int> in_degree(n + 1, 0);
    for (int v = 1; v <= n; v++)
        for (int u : adj[v]) in_degree[u]++;

    queue<int> q;
    for (int v = 1; v <= n; v++)
        if (in_degree[v] == 0) q.push(v);

    vector<int> order;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        order.push_back(v);
        for (int u : adj[v])
            if (--in_degree[u] == 0) q.push(u);
    }
    if ((int)order.size() != n) return {}; // цикл!
    return order;
}
  

⬆ order.size() != n — если обработали меньше n вершин — цикл

Сложность: O(V + E)

Пример: алгоритм Кана

DAG: 1→2, 1→3, 2→4, 3→4, 3→5, 4→6, 5→6  |  in-deg: 1:0, 2:1, 3:1, 4:2, 5:1, 6:2

Этот порядок отличается от DFS-варианта — обе сортировки корректны

Два подхода: когда что?

Задача: Course Schedule

• Прямое применение топологической сортировки
• DFS или Кан
• Если order.size() < n — цикл → IMPOSSIBLE

Задача: подсчёт путей в DAG

// После топосорта
vector<long long> dp(n + 1, 0);
dp[1] = 1;
for (int v : order)
    for (int u : adj[v])
        dp[u] = (dp[u] + dp[v]) % MOD;
cout << dp[n] << "\n";
  

Практика: топологическая сортировка

Задача: минимальная стоимость

Какие алгоритмы вы знаете?

• BFS (невзвешенный граф) — НЕ работает, веса не равны
• Dijkstra — работает, но O((V+E) log V), избыточно
• 0-1 BFS — O(V + E), идеальный выбор

Идея 0-1 BFS

• Обычный BFS: queue (FIFO) — все рёбра равны
• 0-1 BFS: deque (двусторонняя очередь)

Почему не обычный BFS?

Код: 0-1 BFS

// adj[v] = список пар {сосед, вес} (вес = 0 или 1)
vector<vector<pair<int,int>>> adj(n + 1);
vector<int> dist(n + 1, INT_MAX);
deque<int> dq;
dist[s] = 0;
dq.push_back(s);

while (!dq.empty()) {
    int v = dq.front(); dq.pop_front();
    for (auto [u, w] : adj[v]) {
        if (dist[v] + w < dist[u]) {
            dist[u] = dist[v] + w;
            if (w == 0) dq.push_front(u);  // вес 0: в начало
            else        dq.push_back(u);   // вес 1: в конец
        }
    }
}
  

⬆ push_front / push_back — ключевое отличие от BFS

Сложность: O(V + E)

Пример: 0-1 BFS

1—¹→2, 1—⁰→3, 3—⁰→2, 2—¹→4, 3—¹→4, 4—⁰→5

Типичное применение: сетка

Сетка n×m. Ячейки: пустые (.) или стены (#).
Вопрос: минимум стен для слома, чтобы дойти от (1,1) до (n,m)?

Задача: Labyrinth

Практика: 0-1 BFS

Задача: уязвимости сети

Наивный подход: слишком медленный

1. Для каждого ребра (u, v): удалить, проверить связность DFS, вернуть
2. Если стало больше компонент — мост

Сложность: O(E · (V + E))

Можно ли за один DFS?

Инструмент: времена входа (tin)

При DFS каждой вершине присваиваем время входа — номер при первом посещении.

int timer = 0;
vector<int> tin;

void dfs(int v, int parent) {
    tin[v] = timer++;
    // ...
}
      

Обратные рёбра и функция low

• Рёбра дерева DFS — по которым мы проходим
• Обратные рёбра — к уже посещённым предкам

Критерий: когда ребро — мост?

Код: поиск мостов

int timer = 0;
vector<int> tin, low;
vector<bool> visited;
vector<pair<int,int>> bridges;

void dfs(int v, int parent) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    for (int u : adj[v]) {
        if (u == parent) continue;
        if (visited[u]) {
            low[v] = min(low[v], tin[u]);
        } else {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) bridges.push_back({v, u});
        }
    }
}
  

⬆ Разница с обычным DFS: tin, low, и проверка low[u] > tin[v]

Сложность: O(V + E)

Пример: мосты

Граф: 1-2, 2-3, 3-1, 3-4, 4-5, 5-6, 6-4, 6-7

Подводный камень: кратные рёбра

Решение: передавать номер ребра, не parent:

// adj[v] = список пар {сосед, номер_ребра}
void dfs(int v, int parent_edge) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    for (auto [u, edge_id] : adj[v]) {
        if (edge_id == parent_edge) continue;
        // ... (остальное как раньше)
    }
}
  

Точки сочленения

Точка сочленения — вершина, удаление которой разрушает связность.

Два случая:

1. v — корень DFS: точка сочленения ⟺ у v ≥ 2 детей в дереве DFS
2. v — не корень: точка сочленения ⟺ ∃ ребёнок u: low[u] ≥ tin[v]

Код: точки сочленения

int timer = 0;
vector<int> tin, low;
vector<bool> visited;
set<int> cut_points;

void dfs(int v, int parent) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    int children = 0;

    for (int u : adj[v]) {
        if (u == parent) continue;
        if (visited[u]) {
            low[v] = min(low[v], tin[u]);
        } else {
            children++;
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (parent != -1 && low[u] >= tin[v]) {
                cut_points.insert(v);
            }
        }
    }

    if (parent == -1 && children > 1) {
        cut_points.insert(v);
    }
}
  

⬆ Отличия от мостов: children, ≥, проверка корня

Пример: точки сочленения

Тот же граф: 1-2, 2-3, 3-1, 3-4, 4-5, 5-6, 6-4, 6-7

Точки сочленения: 3, 4, 6

Задача: мосты

Прямое применение алгоритма с tin/low.

Практика: мосты и точки сочленения

Задача: разделить на две команды

Когда граф двудольный?

На практике мы не ищем циклы — пробуем раскрасить BFS-ом.

Проверка двудольности: BFS

1. Массив color[], -1 = не раскрашен
2. Для каждой непосещённой вершины v: BFS, красим v в 0
3. Для каждого соседа u:
   • Не раскрашен → красим в 1 - color[v]
   • Раскрашен и color[u] == color[v] → конфликт!
4. Нет конфликтов → двудольный
5. Обходим все компоненты!

Код: проверка двудольности

int n, m;
vector<vector<int>> adj;
vector<int> color;

bool bfs_bipartite(int start) {
    queue<int> q;
    color[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) {
            if (color[u] == -1) { color[u] = 1 - color[v]; q.push(u); }
            else if (color[u] == color[v]) return false;
        }
    }
    return true;
}

bool is_bipartite() {
    color.assign(n + 1, -1);
    for (int v = 1; v <= n; v++)
        if (color[v] == -1 && !bfs_bipartite(v)) return false;
    return true;
}
  

⬆ 1 - color[v] — переключает 0 ↔ 1

Сложность: O(V + E)

Пример: двудольный

Граф: 1-2, 1-4, 2-3, 3-4, 4-5, 5-6

Двудольный! Доли: {1,3,5} и {2,4,6}

Пример: НЕ двудольный

Граф: 1-2, 2-3, 3-1, 3-4, 4-5

Задача: Building Teams

• Прямая задача на двудольность
• BFS-раскраска: color[v] + 1 = номер команды
• Конфликт → IMPOSSIBLE
• Обработать все компоненты!

Зачем двудольность на олимпиадах?

1. Разделение на группы — прямая проверка
2. Максимальное паросоче��ание — алгоритм Куна работает на двудольных графах
3. Раскраска — двудольность = хроматическое число 2
4. Шахматная доска — чёрные/белые клетки = двудольный граф
5. Паттерн: 2 группы + «соседи в разных» → двудольность

Практика: двудольность

Итоги: что мы изучили

Все задачи для практики

Вопросы?