|
Система пересекающихся множеств
(Время: 1 сек. Память: 16 Мб Сложность: 35%)
Самая удобная структура для хранения информации о данных множествах – это двумерный массив a[1..n][1..m], в котором в i-й строке будет храниться информация о элементах множества с номером i, где a[i][j] – логическое значение, соответствующее принадлежности элемента j множеству i.
Исходя из использования вышеупомянутой структуры легко представляется процесс заполнения множеств элементами и реализации команд вывода элементов заданного множества и списка множеств, содержащих заданный элемент. Для добавления элемента j в множество i достаточно выполнить операцию присваивания: a[i][j]=true, а для выполнения остальных операций достаточно вывести i-ю строку или j-й столбец соответственно.
При решении данной задачи следует аккуратным образом считывать и обрабатывать команды ADD, LISTSET и LISTSETOF. Приведем алгоритмическую реализацию решения:
read(m,n,k)
int a[1..n][1..m]={0,…,0}
for t=1..k{
read(s)
if(s="ADD") read(j,i), a[i][j]=true
if(s="LISTSET"){
read(i), f=true
for j=1..m
if(a[i][j]) writeln(j," "), f=false
if(f) write(-1)
writeln
}
if(s="LISTSETSOF"){
read(j), f=true
for i=1..n
if(a[i][j]) writeln(i," "), f=false;
if(f) write(-1)
writeln
}
}
| |
