Разбор задачи «Школа магии»

Идея задачи

У нас есть ориентированный ациклический граф.

• Вершины — это аудитории школы магии.
• Рёбра — это односторонние порталы.
• Нужно найти минимальный набор стартовых аудиторий, из которых можно добраться до всех остальных.

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

Главное наблюдение

Посмотрим на вершину, в которую не входит ни одного ребра.

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

Значит:

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

Отсюда сразу получается решение:

ответ — это все вершины, у которых входящая степень равна нулю.

Что такое входящая степень

Входящая степень вершины — это количество рёбер, которые в неё входят.

Например, если есть рёбра:

• 0 -> 2
• 1 -> 2
• 3 -> 2

то входящая степень вершины 2 равна 3.

Если же в вершину не входит ни одного ребра, её входящая степень равна 0.

Почему решение корректно

Докажем это аккуратно.

1. Все вершины с нулевой входящей степенью обязаны быть в ответе

Пусть вершина v имеет входящую степень 0.

Это значит, что не существует ни одного ребра вида u -> v. Следовательно, из другой вершины попасть в v невозможно.

Значит, если не взять v как стартовую, то эта вершина вообще не будет достижима.

Итак, любая вершина с входящей степенью 0 обязательно должна входить в ответ.

2. Этого набора достаточно

Теперь возьмём любую вершину графа.

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

Так как граф ациклический, если идти назад по рёбрам, мы не можем ходить бесконечно. Рано или поздно мы придём в вершину, в которую уже не входит ни одного ребра.

А такие вершины мы как раз включаем в ответ.

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

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

Алгоритм

1. Создадим массив indegree, где indegree[v] — входящая степень вершины v.
2. Изначально все значения равны 0.
3. Для каждого ребра u -> v увеличим indegree[v] на 1.
4. После этого пройдём по всем вершинам.
5. Все вершины, для которых indegree[v] == 0, добавим в ответ.

Разберём пример

Пусть дан граф:

6 5
0 1
0 2
2 5
3 4
4 2

Посчитаем входящие степени:

• 0: 0
• 1: 1
• 2: 2
• 3: 0
• 4: 1
• 5: 1

Нулевую входящую степень имеют вершины 0 и 3.

Значит, ответ:

0 3

И действительно:

• из 0 можно попасть в 1, 2, 5;
• из 3 можно попасть в 4, а потом в 2 и 5.

Все вершины покрыты.

Реализация на C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> indegree(n, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        indegree[v]++;
    }

    vector<int> answer;
    for (int v = 0; v < n; v++) {
        if (indegree[v] == 0) {
            answer.push_back(v);
        }
    }

    for (int i = 0; i < (int)answer.size(); i++) {
        if (i > 0) cout << ' ';
        cout << answer[i];
    }
    cout << '\n';

    return 0;
}

Реализация на Python

import sys


def solve():
    input = sys.stdin.readline

    n, m = map(int, input().split())
    indegree = [0] * n

    for _ in range(m):
        u, v = map(int, input().split())
        indegree[v] += 1

    answer = []
    for v in range(n):
        if indegree[v] == 0:
            answer.append(v)

    print(*answer)


if __name__ == "__main__":
    solve()

Оценка сложности

Пусть:

• n — количество вершин,
• m — количество рёбер.

Тогда:

• на чтение рёбер и подсчёт входящих степеней уходит O(m);
• на проход по всем вершинам уходит O(n).

Итого:

• время: O(n + m);
• память: O(n).

Типичные ошибки

Ошибка 1. Пытаться запускать обход из каждой вершины

Иногда хочется для каждой вершины делать DFS или BFS и проверять, кого можно достичь.

Такое решение будет слишком тяжёлым: в худшем случае получится O(n * (n + m)), что заметно хуже нужного.

Здесь задача решается намного проще — достаточно посмотреть только на входящие степени.

Ошибка 2. Считать исходящие степени вместо входящих

Нам важно не сколько рёбер выходит из вершины, а сколько входит в неё.

Именно вершины без входящих рёбер нельзя достичь из других.

Ошибка 3. Забыть случай без рёбер

Если m = 0, то ни в одну вершину нельзя попасть из другой. Значит, ответом будут все вершины.

Итог

В этой задаче нужно заметить очень важную идею:

• все вершины, в которые ничего не входит, обязательно должны быть стартовыми;
• все остальные вершины достижимы из них.

После этого решение становится очень коротким:

1. считаем входящие степени;
2. выводим все вершины с нулевой входящей степенью.

Это хороший пример задачи, где правильное наблюдение полностью упрощает решение.