Радиосети экспедиции — разбор задачи

1. Идея

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

Ключевая идея: если несколько вершин образуют сильно связанную компоненту, то, попав в любую вершину этой компоненты, сообщение доберётся до всех вершин внутри неё. Значит, каждую такую компоненту можно считать одной "сверхвершиной".

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

Тогда задача сводится к очень простой:

• у каких компонент в конденсации нет входящих рёбер?
• именно в такие компоненты нужно передать сообщение напрямую хотя бы один раз;
• во все остальные компоненты сообщение сможет прийти из каких-то других.

Ответ — количество компонент конденсации с нулевой входной степенью.

2. Наблюдения

Наблюдение 1. Сильная связность позволяет считать вершины единым блоком

Если из вершины a можно попасть в b, а из b можно попасть в a, то, получив сообщение в одной из них, можно распространить его по всей такой группе.

Поэтому внутри сильной компоненты достаточно "запустить" сообщение один раз.

Наблюдение 2. Между сильными компонентами циклов нет

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

Это важное свойство: в таком графе есть источники, то есть вершины без входящих рёбер.

Наблюдение 3. Каждая компонента-источник должна быть запущена отдельно

Если у компоненты нет входящих рёбер из других компонент, то сообщение не может прийти в неё извне. Значит, надо вручную выдать сообщение хотя бы одному отряду из этой компоненты.

Наблюдение 4. Этого достаточно

Если всем компонентам-источникам выдать сообщение, то дальше по рёбрам конденсации оно распространится во все остальные компоненты.

3. Алгоритм

Будем искать сильные компоненты алгоритмом Косарайю.

Шаг 1. Строим граф и обратный граф

• g — список исходящих рёбер
• gr — список рёбер в обратном графе

Шаг 2. Первый обход DFS по исходному графу

Нужно получить порядок выхода вершин из DFS.

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

Для каждой ещё не посещённой вершины запускаем обход. Когда все её потомки обработаны, добавляем вершину в массив order.

Шаг 3. Второй обход DFS по обратному графу

Рассматриваем вершины в порядке, обратном order.

Если вершина ещё не отнесена ни к какой компоненте, запускаем из неё обход по gr и красим все достижимые вершины в номер текущей компоненты.

Так мы найдём все сильные компоненты.

Шаг 4. Считаем входящие степени компонент

Просматриваем все рёбра u -> v исходного графа.

• если comp[u] == comp[v], то ребро внутреннее, оно нас не интересует;
• если comp[u] != comp[v], то в конденсации есть ребро из comp[u] в comp[v], значит, увеличиваем входящую степень компоненты comp[v].

Шаг 5. Считаем компоненты с нулевой входящей степенью

Ответ — количество компонент, у которых indeg[c] == 0.

4. Почему это работает

Докажем корректность.

1. Каждую сильную компоненту можно рассматривать как одну вершину

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

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

2. После сжатия в сильные компоненты получается DAG

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

3. Каждая компонента с нулевой входящей степенью обязательно требует начальной передачи

Пусть у компоненты C нет входящих рёбер в конденсации.

Тогда не существует другой компоненты, из которой сообщение могло бы попасть в C. Значит, если изначально не передать сообщение ни одной вершине из C, она никогда его не получит.

Следовательно, для каждой такой компоненты нужен хотя бы один стартовый отряд.

4. Компонентам с ненулевой входящей степенью начальная передача не обязательна

Если у компоненты есть входящее ребро, то существует другая компонента, из которой в неё можно попасть.

В DAG, начиная распространение из всех источников, мы обязательно достигнем всех остальных вершин графа. Значит, если выдать сообщение всем компонентам-источникам, то оно дойдёт до всех компонент.

5. Минимальность ответа

• меньше взять нельзя, потому что каждая компонента-источник требует отдельного запуска;
• столько взять достаточно, потому что из всех источников сообщение покроет всю конденсацию.

Значит, число компонент конденсации с нулевой входящей степенью и есть минимальный ответ.

5. Сложность

Пусть n — число вершин, m — число рёбер.

• Построение графа: O(n + m)
• Первый обход: O(n + m)
• Второй обход: O(n + m)
• Подсчёт входящих степеней компонент: O(m)

Итоговая сложность: O(n + m)

Память:

• граф и обратный граф,
• массивы used, order, comp, indeg.

Итого: O(n + m)

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1), gr(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        gr[v].push_back(u);
    }

    vector<int> used(n + 1, 0);
    vector<int> order;
    order.reserve(n);

    for (int s = 1; s <= n; s++) {
        if (used[s]) continue;

        vector<pair<int, int>> st;
        st.push_back({s, 0});
        used[s] = 1;

        while (!st.empty()) {
            int v = st.back().first;
            int &idx = st.back().second;

            if (idx < (int)g[v].size()) {
                int to = g[v][idx++];
                if (!used[to]) {
                    used[to] = 1;
                    st.push_back({to, 0});
                }
            } else {
                order.push_back(v);
                st.pop_back();
            }
        }
    }

    vector<int> comp(n + 1, -1);
    int comps = 0;

    for (int i = n - 1; i >= 0; i--) {
        int s = order[i];
        if (comp[s] != -1) continue;

        vector<int> st;
        st.push_back(s);
        comp[s] = comps;

        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            for (int to : gr[v]) {
                if (comp[to] == -1) {
                    comp[to] = comps;
                    st.push_back(to);
                }
            }
        }

        comps++;
    }

    vector<int> indeg(comps, 0);
    for (int u = 1; u <= n; u++) {
        for (int v : g[u]) {
            if (comp[u] != comp[v]) {
                indeg[comp[v]]++;
            }
        }
    }

    int answer = 0;
    for (int c = 0; c < comps; c++) {
        if (indeg[c] == 0) answer++;
    }

    cout << answer << '\n';
    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())

g = [[] for _ in range(n + 1)]
gr = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    gr[v].append(u)

used = [0] * (n + 1)
order = []

for s in range(1, n + 1):
    if used[s]:
        continue

    stack = [[s, 0]]
    used[s] = 1

    while stack:
        v, idx = stack[-1]
        if idx < len(g[v]):
            to = g[v][idx]
            stack[-1][1] += 1
            if not used[to]:
                used[to] = 1
                stack.append([to, 0])
        else:
            order.append(v)
            stack.pop()

comp = [-1] * (n + 1)
comps = 0

for i in range(n - 1, -1, -1):
    s = order[i]
    if comp[s] != -1:
        continue

    stack = [s]
    comp[s] = comps

    while stack:
        v = stack.pop()
        for to in gr[v]:
            if comp[to] == -1:
                comp[to] = comps
                stack.append(to)

    comps += 1

indeg = [0] * comps

for u in range(1, n + 1):
    cu = comp[u]
    for v in g[u]:
        cv = comp[v]
        if cu != cv:
            indeg[cv] += 1

answer = 0
for x in indeg:
    if x == 0:
        answer += 1

print(answer)