Максимальное множество друзей |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Максимальное множество друзей |
Jekaterina |
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 61 Пол: Женский Реальное имя: Jekaterina Lauce Репутация: 0 |
Доброй ночи! Не справляюсь с задачей: "В стране Н. пользуются порталом "Друзья". Во входном файле в первой строке дается номер максимально возмоной персоны, ниже приведены пары друзей, например:
15 2 4 6 11 2 13 13 2 4 14 Запись 2 4 означает, что персона 2 является другом персоны 4, и т. д. Друзья объединяются в множество друзей: например, из пар 2 4 и 2 13 образуется множество друзей {2, 4, 13}. Цель-отыскать наибольшее множество друзей и вывести его в выходной файл. Я думаю, здесь нужно использовать массив множеств, но не знаю, как правильно описать переменные (такая структура мне раньше не попадалась). Сам алгоритм мне тоже не ясен - может быть, кто-то из вас поймет, как использовать этот максимальный номер в первой строке? (надеюсь, динамические переменные здесь можно не использовать-я с ними пока крайне слабо знакома, а разобраться в решении хочется )Заранее благодарю за помощь! |
Michael_Rybak |
Сообщение
#2
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Сначала сам алгоритм. Пусть есть N человек. Будем использовать N цветов. Изначально человека 1 покрасим в цвет 1, человека 2 - в цвет 2, и т.д. Все люди покрашены в разные цвета.
Дальше идем по списку пар друзей. Читаем очередную пару: А, В. Если цвета А и В совпадают, значит, они и так уже подружились. Если нет - смотрим, каких людей *меньше* - покрашенных в цвет А, или в цвет В. Меньшую группу перекрашиваем в цвет большей. В конце остается выбрать наиболее часто встречающуюся краску. Сложность такого решения, в оптимальной реализации, составит O(n log n), потому что каждый конкретный человек будет при каждом перекрашивании попадать в группу с как минимум в 2 раза большей численностью, и потому будет перекрашен не более [log n] + 1 раз. Но в твоем случае, судя по всему, достаточно и O(n^2). Тогда можно пренебречь условием "Меньшую группу перекрашиваем в цвет большей", и просто перекрашивать А в В. Достаточно объявить один массив: const MAX_N = 128; Решение будет выглядеть примерно так: Read(n); |
Текстовая версия | 26.04.2024 1:49 |