Disjoint Set Операция Find_Set (х) с использованием связанного списка

Question

Его о наивном союзном Найти алгоритм с использованием связанного список представление непересекающихся множеств:
Find_Set (х) операция возвращает указатель на представитель множества, содержащее элемент х , для которого требуется время O (1), поскольку узел, содержащий x, имеет указатель, непосредственно указывающий на представителя x. Но прежде, чем это нужно, нам нужно найти конкретный узел, содержащий элемент x среди всех непересекающихся множеств. Так что этот поиск не является O (1). Я не понимаю, как Find_set (x) является O (1) (как указано в книгах), когда мы не знаем, в каком непересекающемся множестве принадлежит узел, содержащий x.

Answer 1

Предполагается, что каждый элемент содержит некоторый указатель/ссылку на набор, к которому он принадлежит (набор может быть фактически представлен одним из его элементов-членов). Поэтому при запросе Find_Set (x), поскольку у вас уже есть элемент x, вам просто нужно проконсультироваться с этим указателем/ссылкой, а операция - O (1). С реализацией связанного списка, где каждый набор хранится как связанный список элементов, каждый элемент содержит указатель на головку связанного списка, который выбирается как представительский элемент набора.