0 / 0 / 0
Регистрация: 18.06.2020
Сообщений: 17
1

Система непересекающихся множеств

20.06.2020, 09:30. Показов 3632. Ответов 20
Метки нет (Все метки)

Помогите пожалуйста решить эту задачу

Условие:
Напишите программу, которая будет содержать реализацию структуры данных для системы непересекающихся множеств и обрабатывать запросы следующих видов.

«RESET n» — создать систему непересекающихся множеств на элементах от 0 до n−1, причём первое множество будет состоять из одного элемента 0, второе множество — из элемента 1, третье — из элемента 2, ..., последнее — из элемента n−1. Если до этого структура данных уже содержала некоторый набор множеств, то вся информация о них утрачивается. При этом следует вывести два слова через пробел — «RESET DONE».
«JOIN a b» — объединить множества, которым принадлежат элементы a и b. Если элементы и так принадлежали одному множеству, то требуется вывести «ALREADY a b», если же действие можно успешно выполнить, то ничего выводить не следует.
«CHECK a b» — проверить, одному ли множеству принадлежат элементы a и b, и, если одному, то вывести «YES», а иначе — «NO».

Формат входных данных:
Во входных данных содержится последовательность запросов RESET, JOIN и CHECK — каждый в отдельной строке, согласно вышеописанному формату. Гарантировано, что первая строка содержит запрос RESET, а общее количество запросов RESET не превышает 5. Общее количество всех запросов не превышает 250000. Значение n в каждом запросе RESET не превышает 100000. В каждом запросе JOIN и в каждом запросе CHECK оба числа будут в диапазоне от 0 до n−1, где n — параметр последнего выполненного запроса RESET.

Формат выходных данных:
Для запросов RESET, CHECK и тех запросов JOIN, где элементы и так принадлежат одному множеству, выводить на стандартный выход (экран) соответствующий результат (в отдельной строке).

входные данные:
RESET 15
JOIN 14 10
JOIN 13 8
JOIN 0 9
JOIN 8 3
JOIN 4 1
JOIN 10 5
JOIN 8 4
CHECK 2 11
JOIN 4 1
JOIN 2 6
CHECK 9 1
JOIN 6 5
CHECK 10 5

выходные данные:
RESET DONE
NO
ALREADY 4 1
NO
YES
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.06.2020, 09:30
Ответы с готовыми решениями:

Найти подсемейство попарно непересекающихся множеств
Столкнулся с интересно задачей, никак не могу придумать, как сделать. Попрошу помощи у вас, друзья....

Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств
Даны два непересекающихся конечных множества точек на плоскости. Определить окружность, проходящую...

Поиск непересекающихся множеств
Помогите составить алгоритм по поиску непересекающихся множеств, очень надо.

Поиск непересекающихся множеств
помогите составить алгоритм по поиску непересекающихся множеств, вообще никакой информации не могу...

20
316 / 113 / 37
Регистрация: 26.11.2019
Сообщений: 735
22.06.2020, 16:45 21
TheCalligrapher, Возможно вы меня не так поняли(я тут сам виноват), для себя я уже давно решил, что path compression(называйте как хотите) мой оптимальный вариант, а значит все ваши ответы я читал с мыслью: "Ем.... ну... ем, а зачем он использует эти недомеры по-типу 'Немножко исправляем ссылки' ". Позвольте заметить, что при случайном совпадении входных данных таким образом, что сжатие пути перестанет быть таким полезным, многие другие методы(я кстати не знаю почему вы так и не назвали их по своему имени, ведь это все эвристики сжатия пути)будут полезнее, чем оригинальное(и самое дерзкое)сжатие пути. Но такой вариант не предсказать, а стандартное сжатие пути даже тут не покажется себя слишком плохо, так что я рекомендую использовать его всегда, лично меня эта эвристика никогда не подводила. Также если разговор(монолог) уже пошел про эвристики, почему бы не упомянуть и другие, не менее важные вещи, такие как "Эвристика объединения по рангу", ведь эта вещь помогает вашему нелюбимому сжатию пути работать без перебоев и быть самым лучшим

Добавлено через 43 минуты
TheCalligrapher, Не знаю по какой причине, но мой гигантский развернутый ответ не был доставлен, поэтому я думаю завершить спор прямо тут
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.06.2020, 16:45
Помогаю со студенческими работами здесь

Мощность пересечения множеств А и В(непересекающихся)
Подскажите, пожалуйста, как решить данную задачку и объясните ход логики? Условие: Даны...

Реализовать поиск непересекающихся множеств
можно как то в этом коде реализовать Поиск непересекающихся множеств? using System; using...

Поиск минимального острова с системой непересекающихся множеств
Код вроде бы рабочий, но мне нужно чтобы только одно ребро "входило" в одну точку( т.е с системой...

Система уравнений теории множеств
Помогите пож-та решить такую систему....

решение система уравнений в теории множеств
Как решить систему уравнений: _ | A\X=B < |_ AUX=C Где A,B,C-данные множества и...

Система уравнений из теории множеств. Сомнительный ответ
\left\{\begin{matrix}\\ A / x = B\\x / A = C\end{matrix}\right. так же известно,что B\subseteq A...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
21
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru