|
Размер: 2460
Комментарий:
|
← Версия 4 от 2020-09-26 00:04:58 ⇥
Размер: 2409
Комментарий:
|
| Удаления помечены так. | Добавления помечены так. |
| Строка 3: | Строка 3: |
| Вводить построчно разделённые запятыми последовательности натуральных чисел (кортежи), окончание ввода — пустая строка. Числа в строке — идентификаторы людей, которые познакомились (или уже были знакомы) на некоторой вечеринке. Верно ли, что от любого из перечисленных людей можно построить цепочку знакомств к любому другому? Иными словами, если некоторый предмет можно передавать только от знакомого знакомому, то существует ли возможность передать его от произвольного человека произвольному (возможно, в несколько приёмов)? Вывести YES или NO | Вводить построчно разделённые запятыми последовательности натуральных чисел (кортежи), окончание ввода — пустая строка. Числа в строке — идентификаторы людей, которые познакомились (или уже были знакомы) на некоторой вечеринке. Верно ли, что от любого из перечисленных людей можно построить цепочку знакомств к любому другому? Иными словами, если считать каждую пару `x,y` ребром неориентированного графа, является ли этот граф связным? Вывести `YES` или `NO`. |
| Строка 7: | Строка 7: |
| 7,8,9 | 7,8,9, |
| Строка 10: | Строка 10: |
| 5,7 11,3,4 |
5,7, 11,3,4, |
| Строка 15: | Строка 15: |
| Здесь даже три изолированные группы, полностью незнакомые друг другу: `11,2,3,4`; `5,7,8,9` и `36,10`. | Здесь даже три изолированные группы, полностью незнакомые друг другу: `11,2,3,4`; `5,7,8,9` и `36,10`. Обратите внимание на возможные запятые в конце строк. |
| Строка 23: | Строка 23: |
| Подсказка: зто задача на множества. Если нажать пункт «показать комментарии» сверху, откроется спойлер — описание того, я как я решал эту задачу. /* Будем составлять список групп (множеств), в каждой из которых требуемое свойство выполняется. Для каждой группы в списке, если хоть кто-то из очередного введённого множества присутствует в ней, в эту группу добавляется всё множество (люди не напрямую, но знакомы). Если введённое множество не пересекается ни с одной группой, оно добавляется в список отдельно. Если под конец пересечение всех групп в списке */ TODO | Подсказка: зто задача на множества. Если нажать пункт «комментарии» сверху, откроется спойлер — описание того, я как я решал эту задачу. /* Создадим список, в котором будем хранить группы (множества) достижимых друг из друга вершин. Введённое множество объединим со всеми множествами из списка, с которыми оно пересекается (тем самым формируя одну большую группу доступности). Остальные (всё ещё несвязные) группы сложим в новый список, куда затем добавим и сформированную общую группу. Если под конец ввода в списке больше одной группы — ответ «NO», а если одна — «YES» */ |
Вводить построчно разделённые запятыми последовательности натуральных чисел (кортежи), окончание ввода — пустая строка. Числа в строке — идентификаторы людей, которые познакомились (или уже были знакомы) на некоторой вечеринке. Верно ли, что от любого из перечисленных людей можно построить цепочку знакомств к любому другому? Иными словами, если считать каждую пару x,y ребром неориентированного графа, является ли этот граф связным? Вывести YES или NO.
11,2,3 7,8,9, 36,10 4,2 5,7, 11,3,4, 9,5
Здесь даже три изолированные группы, полностью незнакомые друг другу: 11,2,3,4; 5,7,8,9 и 36,10. Обратите внимание на возможные запятые в конце строк.
NO
А вот если добавить ещё одну вечеринку — 11,8,36 — круг знакомств замкнётся.
Подсказка: зто задача на множества. Если нажать пункт «комментарии» сверху, откроется спойлер — описание того, я как я решал эту задачу.