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

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

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

«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

TheCalligrapher, Возможно вы меня не так поняли(я тут сам виноват), для себя я уже давно решил, что path compression(называйте как хотите) мой оптимальный вариант, а значит все ваши ответы я читал с мыслью: "Ем.... ну... ем, а зачем он использует эти недомеры по-типу 'Немножко исправляем ссылки' ". Позвольте заметить, что при случайном совпадении входных данных таким образом, что сжатие пути перестанет быть таким полезным, многие другие методы(я кстати не знаю почему вы так и не назвали их по своему имени, ведь это все эвристики сжатия пути)будут полезнее, чем оригинальное(и самое дерзкое)сжатие пути. Но такой вариант не предсказать, а стандартное сжатие пути даже тут не покажется себя слишком плохо, так что я рекомендую использовать его всегда, лично меня эта эвристика никогда не подводила. Также если разговор(монолог) уже пошел про эвристики, почему бы не упомянуть и другие, не менее важные вещи, такие как "Эвристика объединения по рангу", ведь эта вещь помогает вашему нелюбимому сжатию пути работать без перебоев и быть самым лучшим

Добавлено через 43 минуты
TheCalligrapher, Не знаю по какой причине, но мой гигантский развернутый ответ не был доставлен, поэтому я думаю завершить спор прямо тут

0