Алгоритмы и структуры данных 2 2018/2019/communities
Дополнительные действия
Сообществом назовем группу людей, которые попарно общаются друг с другом. В задании необходимо по графу, где вершина — человек, а ребро — факт общения между людьми, найти 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.