Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 35%)

На вступительном экзамене в один из крупнейших университетов нашей страны Вам предложили реализовать структуру данных для хранения множеств натуральных чисел.

Структура данных должна хранить n множеств, в каждое из которых могут входить натуральные числа от 1 до m, при этом одно и то же число может принадлежать нескольким множествам одновременно. Необходимо реализовать операции добавления элемента в множество, вывода всех элементов множества и вывода номеров всех множеств, в которых лежит данный элемент.

Реализуйте описанную структуру данных.

Входные данные

Первая строка входного файла INPUT.TXT содержит натуральные числа m и n (1 ≤ m, n ≤ 100). Вторая строка входного файла содержит натуральное число k –количество операций со структурой данных, которые необходимо выполнить (0 ≤ k ≤ 105).

Последующие k строк описывают эти операции. Описание операции может иметь один из трех форматов:

  • ADD element set – добавить элемент element (1 ≤ element ≤ m) в множество номер set (1 ≤ set ≤ n);
  • LISTSET set – вывести все элементы множества номер set (1 ≤ set ≤ n);
  • LISTSETSOF element – вывести номера всех множеств, содержащих элемент element (1 ≤ element ≤ m).

Общее количество операций LISTSET и LISTSETSOF не превышает 1000.

Выходные данные

Для каждой операции LISTSET или LISTSETSOF в выходной файл OUTPUT.TXT выведите соответствующий список элементов (или номеров множеств) в порядке возрастания. Если список пуст, выведите -1. Порядок вывода должен соответствовать порядку, в котором операции заданы во входном файле.

Примеры

INPUT.TXTOUTPUT.TXT
110 10
5
ADD 1 1
ADD 1 2
ADD 2 1
LISTSET 1
LISTSETSOF 1
1 2
1 2
210 10
3
ADD 1 1
LISTSET 10
LISTSET 1
-1
1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru