algorithm - 使用链表的不相交集操作 Find_Set(x)

Question

它关于使用不相交集的链表表示的朴素联合查找算法：
Find_Set(x) 操作返回一个指向包含元素 x 的集合的代表的指针。这需要 O(1) 时间，因为包含 x 的节点直接有一个指针指向 x 的代表。但在此之前，首先我们需要在所有不相交的集合中找到包含元素 x 的特定节点。所以这个搜索不是 O(1)。我不明白 Find_set(x) 是 O(1 )（如书中给出的），当我们不知道包含 x 的节点属于哪个不相交集合时。

Answer 1

假设每个元素都包含一些指向它所属集合的指针/引用（该集合实际上可以由其成员元素之一表示）。因此，当查询 Find_Set(x) 时，由于您已经有了元素 x，您只需查询此指针/引用，操作为 O(1)。在链表实现中，每个集合都存储为元素的链表，每个元素都有一个指向链表头部的指针，该链表被选为集合的代表元素。