#2, SPbSU

Очевидно, что как минимум 2 клики в графе уже присутствуют.
Как вариант, у каждой вершины можно посчитать кратность.

Как известно, кратность каждой вершины в изолированной клике меньше на единицу, чем количество вершин в клике.

Кратности вершин можно хранить в хэш-таблице или массиве. Также полезно хранить хэш-таблицу (далее КК) с количеством вершин с определенной кратностью <кратность --- количество>

Также для быстрого доступа к соседям можно хранить матрицу смежности.

Искать сами клики вариант, наверное, не самый лучший, так что будем удалять ребра.

Ребра удалять будем следующим образом:
1) Берем вершину с максимальной кратностью, запоминаем ее соседей, включая ее саму;
2) Проходимся по всем соседям этой вершины и ищем вершину, общих соседей с изначальной вершиной у которой меньше всего;
3) Удаляем ребро между ними, декременируя кратности этих двух вершин и изменяя не более 4 ячеек в КК.

Так будем делать до тех пор, пока в КК не получим 2 ключа --- кратности вершин, причем каждый ключ на 1 меньше, чем значение, и сумма значений которых будет равна количеству вершин, а сумма этих ключей --- (количеству вершин - 2)

Ассимптотика: время O(|V|^2*|E|), память O(|V|^2)