В данной задаче требуется определить, можно ли наладить контакт между несколькими разработчиками таким образом, чтобы любые два контактировали либо напрямую, либо через других разработчиков. Для этого предоставляется список из n разработчиков, у каждого из которых указан порог социальности – количество других разработчиков, с которыми он готов контактировать напрямую.
Для решения задачи можно применить алгоритм графа. Создадим граф, где каждый разработчик представляет собой вершину, а контакты между разработчиками – ребра.
Шаги решения:
1) Считываем количество разработчиков и создаем пустой граф без ребер.
2) Считываем пороги социальности для каждого разработчика и добавляем соответствующее количество ребер с другими разработчиками.
3) Проходимся по всем парам разработчиков и проверяем, существует ли маршрут между ними в графе. Для этого можно использовать поиск в глубину или ширину.
4) Если найден маршрут между любыми двумя разработчиками, выводим “YES”, иначе – выводим “NO”.
Алгоритм имеет временную сложность O(n^2), так как приходится проверять каждую пару разработчиков на наличие возможного маршрута. Память, затрачиваемая на хранение графа, составляет O(n).