Алгоритмы и структуры данных 2 2018/2019/communities

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Сообществом назовем группу людей, которые попарно общаются друг с другом. В задании необходимо по графу, где вершина — человек, а ребро — факт общения между людьми, найти K максимальных (по вложению) клик.

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

Файл имеет вид:

N M

edge[0].from edge[0].to

edge[1].from edge[1].to

...

edge[M-1].from edge[M-1].to

где N — количество вершин, M — количество ребер.

В заготовке на Python реализовано считывание списка ребер из файла.

Также в приложении вы найдете файлы с тестами. Тесты содержат различное количество вершин. Добиваться быстрой работы на всех тестах не требуется. Достаточно покрыть три самых маленьких теста (206, 358, 629). Количество клик в тестах может варьироваться от 10 до 1000. Размер клики не превышает 100.