Треугольники импортов
Пакет A импортирует B и C, а B ещё и C: в графе импортов, если забыть о направлениях, это треугольник. Сколько треугольников в неориентированном графе? Петли не считаются, повторные рёбра — одно ребро.
Второй тест — 379 пакетов стандартной библиотеки Go и их импорты, третий — модули JavaScript этого сайта, четвёртый — улицы центра Алматы. Дальше графы, где один узел связан со всеми: так бывает, когда весь код импортирует одну библиотеку.
Вход
В первой строке n и m (1 ≤ n ≤ 2·10⁵, 0 ≤ m ≤ 2·10⁵), дальше m рёбер — пар номеров вершин от 0 до n − 1.
Выход
Число треугольников.
Примеры
Пример 1
5 8 0 1 1 2 2 0 2 3 3 0 3 4 1 1 0 1
2
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Простой способ — для каждой вершины перебрать пары её соседей. Сколько это стоит для вершины, у которой сто тысяч соседей? Как сделать так, чтобы ни у одной вершины не приходилось перебирать много соседей?
2Идея
Направим каждое ребро от вершины с меньшей степенью к вершине с большей (при равных — от меньшего номера). Каждый треугольник получит ровно одну вершину, из которой выходят оба его ребра, — «наименьшую» из трёх, — и найдётся ровно один раз: перебираем у вершины v исходящих соседей w, у них — исходящих соседей x, и проверяем, есть ли ребро v → x.
3Разбор
Почему так быстро? У любой вершины не больше √(2m) исходящих рёбер. Если у v исходящих d, то у всех её исходящих соседей степень не меньше d, а сумма всех степеней — 2m; значит, d·d ≤ 2m. Перебор пар «ребро v → w и исходящее ребро w» стоит O(m·√m).
Проверка «есть ли ребро v → x» — отметка: перед работой с v пометим всех её исходящих соседей числом v, и проверка станет одним чтением массива. Это тот случай, когда выбор представления графа решает задачу: списки исходящих рёбер плюс массив отметок вместо матрицы, которой на 2·10⁵ вершин не хватило бы памяти.
3+Решение
4Сложность
O(m·√m) времени и O(n + m) памяти.
5Типичные ошибки
- Пары соседей у каждой вершины. Пятый тест — узел со 100 000 соседей: 5·10⁹ пар.
- Каждый треугольник трижды. Перебор без направлений находит треугольник из каждой его вершины.
- Повторные рёбра и петли. В первом примере ребро 0–1 записано дважды, а 1–1 — петля; треугольников там два.