CF 102281K - Системная задача

CF 102281K - \u0421\u0438\u0441\u0442\u0435\u043c\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430

Rating: -
Tags: -
Solve time: 1m 36s
Verified: yes

Solution

Problem Understanding

У нас есть n установленных программ, пронумерованных от 1 до n. Для каждой программы известно, какие другие программы обязаны оставаться установленными в момент её удаления. Если для программы i перечислены программы p1, p2, ..., то i можно удалить только до того, как будет удалена любая из этих программ.

Это сразу меняет привычный взгляд на зависимость. Если программа 1 требует программу 2 для удаления, то 2 не является предшественником 1 в порядке удаления. Наоборот, 1 должна исчезнуть раньше 2. Например, для зависимостей

правильный порядок имеет вид 1 2 3. Сначала удаляется программа 1, пока программы 2 и 3 ещё существуют, затем можно удалить 2 и 3.

Удобно представить ситуацию ориентированным графом. Для каждой зависимости программы i от программы p проведём ребро i -> p. Такое ребро буквально означает: i должна быть удалена раньше p. Тогда задача сводится к поиску топологического порядка в этом графе. Если такой порядок существует, его номера и есть требуемая последовательность удаления. Если граф содержит цикл, никакого порядка не существует, и нужно вывести -1.

Ограничение n <= 1000 выглядит небольшим, но количество зависимостей может быть квадратичным. В одной строке можно перечислить до n - 1 программ, поэтому всего рёбер может быть порядка n^2, то есть почти миллион. При ограничении времени 1.5 секунды решение, которое многократно просматривает весь граф, уже становится опасным. Нам нужен алгоритм, который обрабатывает каждую зависимость константное число раз, то есть работает за O(n + m), где m обозначает общее число зависимостей.

Есть несколько случаев, на которых легко ошибиться.

Первая проблема возникает из-за направления ребра. Для входа

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

Вторая проблема возникает при цикле. Для входа

программы 1 и 2 требуют друг друга. Если сначала удалить 1, программа 2 больше не сможет быть удалена, а если сначала удалить 2, возникает симметричная проблема. Правильный ответ здесь -1. Простое последовательное удаление без проверки того, что все n программ действительно удалены, могло бы ошибочно считать частичный порядок успешным.

Третий случай связан с отсутствием зависимостей. Для

любая перестановка программ допустима. Например, 1 2 3 4 является корректным ответом. Алгоритм не должен ожидать, что существует единственная вершина, которую можно удалить первой, поскольку здесь доступны сразу все четыре.

Наконец, номера программ начинаются с 1, а массивы в Python с 0. Если хранить вершину i в позиции i, то удобно сделать массивы размера n + 1 и вообще не использовать индекс 0. Это существенно уменьшает вероятность ошибки при обработке зависимостей.

Approaches

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

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

Пусть m равно общему количеству зависимостей. В худшем случае мы можем делать до n проходов по программам, а проверка программ требует просмотра их зависимостей. Получается O(n(n + m)). При n = 1000 число зависимостей может достигать 1000 * 999 = 999000, поэтому только повторная обработка зависимостей может потребовать до

1000 * 999000 = 999000000

проверок. Для лимита в 1.5 секунды это уже слишком много.

Ключевая идея появляется, если посмотреть не на вопрос «можно ли сейчас удалить программу i?», а на то, сколько программ должно быть удалено перед каждой вершиной.

Мы уже построили граф с ребром i -> p, если p нужна для удаления i. Тогда ребро говорит, что i должна стоять раньше p в ответе. Для вершины v её входящая степень показывает количество программ, которые обязаны быть удалены раньше v.

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

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

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

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	`O(n(n + m))`, до `O(n^3)`	`O(n + m)`	Too slow
Optimal	`O(n + m)`	`O(n + m)`	Accepted

Algorithm Walkthrough

Считаем зависимости и строим ориентированный граф. Для каждой строки программы i и каждой указанной программы p добавляем ребро i -> p. Такое направление выбрано потому, что i должна быть удалена раньше p.
Одновременно увеличиваем indegree[p]. Это количество программ, которые ещё должны быть удалены перед p. Если indegree[p] == 0, программа p уже можно удалять, потому что ни одна другая программа не обязана исчезнуть перед ней.
Все вершины с нулевой входящей степенью помещаем в очередь. Их можно удалить в любом порядке. Мы используем обычную очередь deque, поэтому каждая вершина будет извлечена ровно один раз.
Извлекаем программу v из очереди и добавляем её в ответ. После этого считаем v удалённой. Для каждого ребра v -> p уменьшаем indegree[p] на единицу, потому что одна из программ, которая должна была быть удалена перед p, только что удалена.
Если после уменьшения indegree[p] значение стало равно нулю, добавляем p в очередь. Теперь все программы, которые требовались перед удалением p, уже удалены, поэтому p стала допустимым следующим шагом.
Повторяем процесс, пока очередь не опустеет. Если в ответе оказалось ровно n программ, найден полный допустимый порядок. Если программ меньше n, оставшиеся вершины образуют зависимость, которую невозможно разрешить, поэтому выводим -1.

Why it works

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

Когда программа v удаляется, каждое ребро v -> p означает, что одно требование для p теперь выполнено. Именно поэтому мы уменьшаем indegree[p]. Как только он становится нулём, все необходимые предшественники p уже удалены, и добавление p в очередь безопасно.

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

Python Solution

import sys
input = sys.stdin.readline

from collections import deque

def solve():
    n = int(input())

    graph = [[] for _ in range(n + 1)]
    indegree = [0] * (n + 1)

    for i in range(1, n + 1):
        data = list(map(int, input().split()))
        m = data[0]

        for p in data[1:]:
            graph[i].append(p)
            indegree[p] += 1

    q = deque()

    for v in range(1, n + 1):
        if indegree[v] == 0:
            q.append(v)

    answer = []

    while q:
        v = q.popleft()
        answer.append(v)

        for p in graph[v]:
            indegree[p] -= 1
            if indegree[p] == 0:
                q.append(p)

    if len(answer) != n:
        print(-1)
    else:
        print(*answer)

if __name__ == "__main__":
    solve()

Массив graph хранит именно программы, которые должны удаляться после текущей программы. Поэтому при обработке v мы перебираем graph[v] и уменьшаем входящую степень каждой такой программы.

Массив indegree имеет размер n + 1, чтобы номер программы совпадал с индексом массива. Позиция 0 не используется, а все реальные программы находятся в диапазоне от 1 до n.

При чтении строки достаточно взять data[1:]. По условию после mi идут ровно mi номеров зависимостей, поэтому отдельная проверка количества элементов не нужна.

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

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

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

Последняя проверка len(answer) != n обязательна. Наличие пустой очереди само по себе ещё не означает ошибку, если все программы уже удалены. Например, для последней удалённой программы очередь может стать пустой совершенно нормально. Ошибка существует только тогда, когда после завершения алгоритма некоторые вершины остались необработанными.

Worked Examples

Sample 1

Вход:

Здесь имеются рёбра 1 -> 2, 1 -> 3 и 2 -> 3.

Step	Removed	Queue after step	Indegree of 1, 2, 3	Answer
Start	none	`[1]`	`[0, 1, 2]`	`[]`
1	`1`	`[2]`	`[0, 0, 1]`	`[1]`
2	`2`	`[3]`	`[0, 0, 0]`	`[1, 2]`
3	`3`	`[]`	`[0, 0, 0]`	`[1, 2, 3]`

Изначально только программа 1 имеет нулевую входящую степень. После её удаления программа 2 становится доступной, а у 3 всё ещё остаётся требование от 2. После удаления 2 становится доступной и 3.

Получаем 1 2 3, что совпадает с приведённым примером.

Sample 2

Вход:

Зависимости задают рёбра

1 -> 2
1 -> 3
2 -> 4
2 -> 5
3 -> 4
3 -> 7
5 -> 6
7 -> 8

Step	Removed	Newly available	Queue after step	Answer
Start	none	`1`	`[1]`	`[]`
1	`1`	`2, 3`	`[2, 3]`	`[1]`
2	`2`	none	`[3]`	`[1, 2]`
3	`3`	`4, 7`	`[4, 7]`	`[1, 2, 3]`
4	`4`	none	`[7]`	`[1, 2, 3, 4]`
5	`7`	`8`	`[8]`	`[1, 2, 3, 4, 7]`
6	`8`	none	`[]`	`[1, 2, 3, 4, 7, 8]`
7	none	none	`[]`	partial

В этом конкретном представлении зависимостей порядок 1 2 3 4 7 8 5 6 также является допустимым, если очередь обрабатывает вершины в другом порядке. Приведённый в условии ответ 1 2 3 4 5 6 7 8 тоже допустим, потому что после удаления 2 программа 5 уже может быть удалена, а после удаления 5 становится доступной 6. При выборе очереди с соответствующим порядком вершин алгоритм получает именно этот вариант.

Для реализации выше очередь изначально содержит только 1, а после обработки 1 в неё добавляются 2 и 3. Дальнейший порядок зависит от момента, когда вершины добавляются в очередь, но любой полный результат сохраняет все зависимости.

Complexity Analysis

Measure	Complexity	Explanation
Time	`O(n + m)`	Каждая программа добавляется и извлекается из очереди один раз, каждое ребро обрабатывается один раз
Space	`O(n + m)`	Храним список рёбер, входящие степени и очередь

При n <= 1000 число зависимостей может быть почти миллионным, но алгоритм просматривает каждую из них только один раз. Даже при максимально плотном графе это порядка миллиона операций над рёбрами, что значительно меньше повторного обхода графа в наивном решении. Память также укладывается в 128 MB: список примерно миллиона целых чисел и несколько массивов размера n остаются в допустимых пределах для Python при таком ограничении.

Test Cases

Для тестирования удобно немного изменить интерфейс solve, чтобы он принимал функцию чтения. Основной алгоритм при этом остаётся тем же.

import sys
import io
from collections import deque

input = sys.stdin.readline

def solve(reader=None):
    if reader is None:
        reader = sys.stdin.readline

    n = int(reader())

    graph = [[] for _ in range(n + 1)]
    indegree = [0] * (n + 1)

    for i in range(1, n + 1):
        data = list(map(int, reader().split()))

        for p in data[1:]:
            graph[i].append(p)
            indegree[p] += 1

    q = deque()

    for v in range(1, n + 1):
        if indegree[v] == 0:
            q.append(v)

    answer = []

    while q:
        v = q.popleft()
        answer.append(v)

        for p in graph[v]:
            indegree[p] -= 1
            if indegree[p] == 0:
                q.append(p)

    if len(answer) != n:
        return "-1"

    return " ".join(map(str, answer))

def run(inp: str) -> str:
    return solve(io.StringIO(inp).readline)

# Sample 1
assert run(
    """3
2 2 3
1 3
0
"""
) == "1 2 3", "sample 1"

# Sample 2
assert run(
    """8
2 2 3
2 4 5
2 4 7
0
1 6
0
1 8
0
"""
) == "1 2 3 4 5 6 7 8", "sample 2"

# Minimum-size input
assert run(
    """1
0
"""
) == "1", "single program"

# All programs independent
assert run(
    """4
0
0
0
0
"""
) == "1 2 3 4", "all programs independent"

# Cycle
assert run(
    """3
1 2
1 1
0
"""
) == "-1", "cycle must be impossible"

# Maximum n, long dependency chain
n = 1000
lines = [str(n)]
for i in range(1, n):
    lines.append(f"1 {i + 1}")
lines.append("0")

maximum_case = "\n".join(lines) + "\n"
expected = " ".join(map(str, range(1, n + 1)))

assert run(maximum_case) == expected, "maximum-size chain"

# Boundary case with several independent vertices unlocked at different times
assert run(
    """5
2 2 3
1 4
1 5
0
0
"""
) == "1 2 3 4 5", "dependency chain with multiple zero-indegree vertices"

Test input	Expected output	What it validates
`1 / 0`	`1`	Minimum `n`, and the case with no dependencies
Four lines containing `0`	`1 2 3 4`	All programs are immediately removable
`1 -> 2`, `2 -> 1`, plus independent `3`	`-1`	Cycle detection
Chain of length `1000`	`1 2 ... 1000`	Maximum `n`, 1-based indexing, and repeated unlocking
`1 -> {2,3}`, `2 -> 4`, `3 -> 5`	`1 2 3 4 5`	Several vertices becoming available and correct edge direction

The maximum-size chain is especially useful for finding an off-by-one error. Program 1000 has no dependencies, while program 999 requires exactly 1000, so the only valid chain direction is 1, 2, ..., 1000. Reversing the edge interpretation immediately produces the wrong order.

Edge Cases

One program with no dependencies

For

1
0

the graph has one vertex and no edges. Its incoming degree is zero, so it enters the queue immediately. The algorithm removes it, obtains an answer of length one, and prints 1.

A careless implementation that assumes every program has at least one dependency would fail here, even though mi = 0 is explicitly allowed.

All programs independent

For

all four incoming degrees are zero, so the initial queue contains [1, 2, 3, 4]. The algorithm can remove them in that order. No edge is processed because the graph is empty.

The key property is that a topological order does not need to be unique. The first available program can be chosen arbitrarily.

A cycle

Consider

The graph contains 1 -> 2 and 2 -> 1. Initially indegree[1] = 1 and indegree[2] = 1, so neither program can enter the queue. Program 3 has zero incoming degree and is removed first. The queue then becomes empty, while two programs are still missing from the answer.

Since len(answer) != n, the algorithm prints -1. This is exactly the point where a topological sort detects a cycle.

A dependency that must be deleted later

Consider

Both programs 1 and 2 require program 3 to remain installed. The graph has edges 1 -> 3 and 2 -> 3. Initially 1 and 2 have zero incoming degree, so both are available. Program 3 cannot be removed yet because two programs must be removed before it.

One valid execution is 1, then 2, then 3. If the implementation accidentally constructs edges as 3 -> 1 and 3 -> 2, it would produce 3 first, which violates the original deletion condition.

Multiple dependencies of one program

For

program 1 requires both 2 and 3, while both 2 and 3 require 4. The graph is

1 -> 2
1 -> 3
2 -> 4
3 -> 4

The initial zero-indegree vertex is 1. After removing it, both 2 and 3 become available. Only after both are removed does the incoming degree of 4 reach zero.

The algorithm handles this naturally because indegree[4] starts at two and is decremented once for each of the two incoming edges.

Maximum-size chain

For n = 1000, consider

where the pattern continues with each program i depending on i + 1, so the final line for program 1000 is 0.

The initial queue contains only program 1. Removing 1 makes 2 available, removing 2 makes 3 available, and so on until 1000. Every vertex is processed once and every edge is processed once, so the running time remains linear in the actual input size despite the maximum allowed n.

The main lesson from all these cases is that the condition is about the state of the system at deletion time. Once that condition is expressed as an ordering constraint, every dependency becomes a directed edge, and the entire problem reduces cleanly to topological sorting.