Популярность

Несколько учеников 10А класса физико-математической школы поспорили, кто из них
самый популярный в школе. В 10А были собраны самые способные ребята, поэтому они
сразу же осознали необходимость введения терминологической базы для того, чтобы спор
оставался конструктивным. После долгих обсуждений было принято следующее определение
популярности:
Популярность ученика X определяется числом P – количеством учеников, которые
являются друзьями ученика X или же являются друзьями друзей ученика X за исключением
самого ученика X.
Ваша задача – помочь ученикам 10А установить истину в их споре.
Входные данные
В первой строке входного файла через пробел записаны два целых числа N и K
(1 ≤ N ≤ 103
, 1 ≤ K ≤ 105
) – общее кол-во учеников в школе и количество пар друзей.
В каждой из следующих K строк через пробел записано по два целых числа Xi и Yi
(1 ≤ Xi, Yi ≤ N) – номера учеников, которые являются друзьями (если Xi дружит с Yi, то Yi также
дружит с Xi).
Выходные данные
В первой строке выходного файла необходимо через пробел вывести два целых числа
P и M, где P – максимальная популярность среди учеников школы, а M – количество
учеников, имеющих максимальную популярность.
Во второй строке выходного файла через пробел необходимо вывести по возрастанию
значений M целых чисел Zi – номера учеников школы, имеющих наибольшую популярность.
Пример входного файла
(stdin / input.txt)
10 5
1 3
6 5
3 5
6 3
5 2
Пример выходного файла
(stdout / output.txt)
4 3
3 5 6

0

karslava, И что конкретно у Вас не получается?

0

Я бы лично начал с построения матрицы смежности графа (список списков)..

0

Вот пояснение к примеру:

0

Мне не понятно, как узнать что у человека есть друг друга?
Прибавлять кол-во друзей всех друзей, среди которых ты несколько раз сам и ещё друзья, с которыми ты лично дружишь.
Это не выход!

0

Найти сначала всех "прямых" друзей.
1: {3}
2: {5}
3: {1, 5, 6}
4: set()
5: {2, 3, 6}
6: {3, 5}
7: set()
8: set()
9: set()
10: set()

А потом добавить друзей друзей:
1 : {3, 5, 6}
2 : {3, 5, 6}
3 : {1, 2, 5, 6}
4 : set()
5 : {1, 2, 3, 6}
6 : {1, 2, 3, 5}
7 : set()
8 : set()
9 : set()
10 : set()

Напишите как найти "прямых" друзей.

0

Добавлять единицу элементу если видишь его.
Т.е. если во входных данных пишут 2 6, то 2 и 6 элементу добавляем единицу.

0