CS
Задачник Базовый курс EN

Задача

Все остовные деревья

подсчёт вариантов линейная алгебра теория чисел граф матрица

Городская служба хочет знать, насколько «запасная» сеть улиц района: сколькими способами можно оставить открытыми часть улиц так, чтобы между любыми двумя перекрёстками по-прежнему был проезд, но ни одного кольца не осталось. Каждый такой набор улиц — остовное дерево графа. Две улицы между одними и теми же перекрёстками считаются разными, и деревья, которые различаются выбором одной из них, — тоже разными.

Для района из нескольких десятков перекрёстков ответ легко выходит за 64 бита, а для полного графа на 30 вершинах в нём 42 цифры. Нужно точное число.

Вход

В первой строке число перекрёстков n и число улиц m (1 ≤ n ≤ 80, 0 ≤ m ≤ 1000). В каждой из следующих m строк — два различных номера перекрёстков u и v (1 ≤ u, v ≤ n), которые соединяет улица. Между одной парой перекрёстков может быть несколько улиц.

Выход

Одно число — количество остовных деревьев. Если граф несвязен, их нет, и ответ 0; у графа из одной вершины ровно одно дерево — без улиц.

Примеры

Пример 1

Вход
4 5
1 2
2 3
3 4
4 1
1 3
Выход
8

Ограничения

Время · Python
8000 мс
Время · Go
2000 мс
Память
256 МБ
Проверка
11 тестов

Разбор

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

1Подсказка 1

Перебирать подмножества улиц бессмысленно: их 2m. Число остовных деревьев даёт формула Кирхгофа — определитель матрицы, где на диагонали степени вершин, а для каждой улицы uv в клетках (u, v) и (v, u) стоит −1, без одной строки и такого же столбца. Как посчитать определитель точно, если он из сотни цифр?

2Подсказка 2

Метод Гаусса в числах с плавающей точкой даёт только первые 15–16 цифр. Определитель целый — значит, его можно посчитать по модулю нескольких простых чисел. Сколько модулей нужно, чтобы восстановить ответ однозначно?

3Идея

Считаем определитель по модулю простых p₁, p₂, … методом Гаусса — деление заменяется умножением на обратный элемент — и восстанавливаем ответ по остаткам алгоритмом Гарнера. Модулей нужно столько, чтобы их произведение превысило ответ, и границу даёт простое наблюдение: деревьев не больше произведения степеней всех вершин, кроме одной. Каждое дерево однозначно задаётся тем, какое ребро ведёт от каждой вершины к корню.

4Разбор

Строим матрицу Кирхгофа L, вычёркиваем последнюю строку и последний столбец. Граница B — произведение степеней вершин 1…n − 1 (если какая-то степень нулевая, граф несвязен, граница ноль и ответ ноль). Берём простые модули сверху вниз, пока их произведение не превысит B, по каждому считаем определитель: в столбце ищем ненулевой элемент, меняем строки (знак определителя меняется), домножаем определитель на ведущий элемент и вычитаем строку, умноженную на arc·acc⁻¹, из нижних строк.

В эталоне на Python модули — простые чуть меньше 2⁶¹: длинная арифметика бесплатна, и чем модуль длиннее, тем меньше их нужно — здесь не больше семи. В Go модули меньше 2³¹: тогда произведение двух остатков помещается в uint64, а math/big нужен только для сборки ответа и границы. Если граф несвязен, определитель равен нулю по любому модулю, и Гарнер возвращает ноль.

Можно обойтись и без модулей: метод Барейсса считает определитель целочисленной матрицы в целых числах, деля на предыдущий ведущий элемент нацело, а дроби Python сокращаются сами. На таких размерах оба способа укладываются в лимит; в статье есть замер, где какой быстрее.

4+Решение
5Сложность

O(n³) операций на каждый модуль; модулей O(n log D / log p), где D — наибольшая степень. Сборка алгоритмом Гарнера — O(k²) для k модулей.

6Типичные ошибки
  • Числа с плавающей точкой. Для полного графа на 30 вершинах ответ 30²⁸ — 42 цифры, и double сохранит из них шестнадцать. Округление в конце не спасает.
  • Мало модулей. Если взять модулей «на глаз», Гарнер вернёт остаток ответа по их произведению — правдоподобное и неверное число.
  • Кратные улицы. Две улицы между одной парой перекрёстков дают в клетке −2, а не −1, и степень вершины растёт на два. Ответ для двух вершин и тысячи улиц между ними — 1000.
  • Одна вершина. Матрица без строки и столбца пустая, её определитель — 1. Отдельный случай удобнее разобрать сразу.

Алгоритмы задачи

NUM Алгоритм Китайская теорема об остатках Число по остаткам от нескольких модулей: алгоритм Гарнера и точные вычисления по многим простым. O(k²) операций с машинными числами 2 задачи NUM Алгоритм Метод Гаусса Линейная система исключением: ведущий элемент, LU, обусловленность, разреженные матрицы и заполнение. O(n³): около n³/3 умножений на прямой ход 2 задачи
Каталог алгоритмов