В стране есть столица и остальные города. Оказалось, что каждый город, соединенный со столицей прямой дорогой, соединен прямой дорогой ровно с 40 городами (включая столицу), а каждый нестоличный город соединен прямыми дорогами ровно с половиной городов, которые соединены дорогами со столицей. Сколько может быть городов в стране?
Обозначим через “столицу” одну вершину, а все остальные города – вершины графа. Пусть у столицы есть соседи (то есть города, с которыми она соединена дорогой) – их обозначим через A, а число таких городов равно n. Тогда остальные (нестоличные) города поделятся на две группы: те, что соединены с столицей (группа A), и те, что не соединены с ней – обозначим их через B, их число m.
Даны два условия (дороги – неориентированные, без кратных ребер):
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
