Перебор классов в структуре данных с непересекающимся множеством

Question

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

При поиске в Интернете я не нашел никакой полезной информации о наилучшем способе реализовать это или как это влияет на сложность. Я весьма удивлен, так как это кажется чем-то, что понадобится довольно часто.

Есть ли стандартный способ сделать это? Я думаю об использовании связанного списка (я использую C, поэтому я планирую хранить несколько указателей в верхнем элементе каждого класса эквивалентности) и обновляю его при каждой операции объединения. Есть ли лучший способ?

Answer 1

Ваше предложение кажется очень разумным. Если вы пропустили список с двумя связями через представителей, вы можете склеить элемент из списка представителей за время O (1), а затем обходить список каждый раз, когда вам нужно вывести список представителей.

@ ardenit has упомянул, что вы также можете использовать внешнюю таблицу ha sh или BST для хранения представителей. Это, конечно, проще кодировать, хотя я подозреваю, что это будет не так быстро, как простое продвижение связанного списка через элементы.

Answer 2

Вы можете хранить указатели на верхние элементы в наборе на основе ha sh или в любом сбалансированном бинарном дереве поиска. Вам нужно только удалить и добавить элементы - обе операции в этих структурах выполняются в O(1)* и O(logN) соответственно. В связанном списке они запускаются в O(N).