Python задача Команда мэра

Вот я набросал вариант с консольным вводом. Не понятно, что Вам уже доступно. Тут есть словари и множества.

исправлено

 n = int(input())
 k = int(input())

frends = {} #словарь, ключи - друзья, значения множество друзей. В начале сам себе друг
for i in range(1, n + 1):
    frends[i] = {i}

while k > 0: # Вводим k пар и добавляем в множество друзей для каждого из пары
    temp = list(map(int, input().split()))
    frends[temp[0]].add(temp[1])
    frends[temp[1]].add(temp[0])
    k -= 1

# Для всех друзей ищем людей с таким же множеством друзей и среди них ищем максимально большое количество.
maxteam = []
for frend in frends:
    team = []
    for i in range(1, n + 1):
        if frends[frend].issubset(frends[i]):
            team.append(i)
    if len(team) > len(maxteam):
        maxteam = team
maxteam.sort()
print(len(maxteam))
print(*maxteam)

Задачу следует рассматривать с точки зрения теории графов (как самой удобной для отображения взаимоотношений в группе), а конкретнее клики из этой теории. Как говорит нам Википедия:

Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе (Задача о клике) является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы дл

Т.е. то, что нам и нужно найти. Опять идем на Википедию:

Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 1973 году и до сих пор является одним из самых эффективных алгоритмов поиска клик.

ПРОЦЕДУРА extend (candidates, not):
  ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates, 
  ВЫПОЛНЯТЬ:
  1 Выбираем вершину v из candidates и добавляем её в compsub
  2 Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v
  3 ЕСЛИ new_candidates и new_not пусты
  4 ТО compsub – клика
  5 ИНАЧЕ рекурсивно вызываем extend (new_candidates, new_not)
  6 Удаляем v из compsub и candidates, и помещаем в not

Эффективность, то что нам нужно :). Итак сначала из полученных данных составляем "список отношений" для всех членов группы:

def foo(couples):
    friendship = {}
    counter = 0
    while counter < len(couples):
        current = couples[counter][0]
        if current not in friendship.keys():
            for a, b in couples:
                if a == current:
                    friendship.setdefault(a, []).append(b)
                if b == current:
                    friendship.setdefault(b, []).append(a)
        counter += 1
    return friendship

Для таких входящих условий:

couples = [(1, 2), (2, 3), (1, 6), (2, 6), (1, 3), (3, 5), (1, 5), (5, 2), (6, 4)]

Получим:

{1: [2, 6, 3, 5], 2: [1, 3, 6, 5], 3: [2, 1, 5], 5: [3, 1, 2], 6: [1, 2, 4]}

Теперь начинаем обрабатывать сформированные данные по указанному выше алгоритму (код честно утащен отсюда):

def BronKerbosch(P, R=None, X=None):
    P = set(P)
    R = set() if R is None else R
    X = set() if X is None else X
    if not P and not X:
        yield R
    while P:
        v = P.pop()
        yield from BronKerbosch(
            P=P.intersection(n[v]), R=R.union([v]), X=X.intersection(n[v]))
        X.add(v)

Все что нам остается - это получить и выдать результат:

couples = [(1, 2), (2, 3), (1, 6), (2, 6), (1, 3), (3, 5), (1, 5), (5, 2), (6, 4)]
n = foo(couples)
P = n.keys()
res = max(list(BronKerbosch(P)))
print(len(res))
output = " ".join(str(x) for x in res)
print(output)

Вывод:

4
1 2 3 5

Как-то так. Код не оптимальный, прошу тапками не кидаться