Прямые рейсы
Аэропорты пронумерованы от 1 до n; некоторые пары связаны прямыми рейсами в обе стороны. Найдите самую большую группу аэропортов, в которой каждые два связаны прямым рейсом.
Третий тест — настоящая сеть рейсов: 3468 аэропортов и все пары, между которыми летают в обе стороны; четвёртый — 200 самых связанных из них. Остальные тесты — плотные графы, где таких групп много и они переплетены.
Вход
В первой строке n и m (1 ≤ n ≤ 3500, 0 ≤ m ≤ 5 · 10⁴). Дальше m строк — пары связанных аэропортов, каждая один раз. В тестах, где n больше 200, граф разреженный.
Выход
В первой строке — размер группы k, во второй — k номеров аэропортов. Если групп наибольшего размера несколько, выведите любую.
Примеры
Пример 1
6 9 1 2 1 3 2 3 3 4 3 5 3 6 4 5 4 6 5 6
4 3 4 5 6
Пример 2
4 2 1 2 3 4
2 3 4
Ограничения
- Время · Python
- 12500 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это задача о наибольшей клике, и быстрого алгоритма для неё нет. Остаётся перебор — добавлять вершины, связанные со всеми уже взятыми. Как не открывать ветви, где больше рекорда не набрать?
2Подсказка 2
«Взято плюс все кандидаты» — слабая оценка: в плотном графе кандидатов сотня, а клика — двадцать. Раскрасьте кандидатов так, чтобы вершины одного цвета не были соседями. Сколько вершин клики может быть одного цвета?
3Идея
Ветви и границы с оценкой раскраской: клика не больше числа цветов, ведь её вершины попарно соседи и потому разных цветов. Раскраска жадная, в каждом узле заново; кандидатов перебираем от старшего цвета к младшему, и номер цвета текущей вершины — оценка для всего, что осталось.
4Разбор
Начальный порядок — по убыванию степени. В узле раскрашиваем кандидатов, выписываем их по цветам и снимаем с конца: если «взято + цвет» не больше рекорда, ветвь закончена; иначе берём вершину, оставляем среди не снятых её соседей и спускаемся. Глубина рекурсии не больше размера клики — меньше сорока.
4+Решение
5Сложность
Экспоненциально в худшем случае, но на тестах дерево поиска — от 242 узлов на сети рейсов до 27 тысяч на самом трудном плотном графе. Раскраска стоит O(k²) сравнений на узел с k кандидатами.
6Типичные ошибки
- Оценка числом кандидатов. Это
wrong.py. На сети рейсов она успевает — граф разреженный, — а на плотных графах с пятого теста перебор разрастается до миллионов узлов. - Раскраска один раз. Если раскрасить только в корне, оценка внутри ветвей грубеет: в подграфе нужно меньше цветов, чем во всём графе.
- Строгое сравнение. Отсекать нужно, когда «взято + цвет» не больше рекорда; со строгим знаком ответ верен, но дерево заметно больше.
- Жадность. «Брать вершину, у которой больше всего соседей среди оставшихся кандидатов» даёт большую клику, но не наибольшую: на сети рейсов — 35 аэропортов вместо 38, на седьмом тесте — 19 вместо 22. Как первый рекорд она полезна.