Disjoint Set Operation Find_Set(x) using linked list

Question

Its about naive Union-Find algorithm using linked-list representation of disjoint sets:
Find_Set(x) operation returns a pointer to the representative of the set containing element x.which requires O(1) time, since node containing x has a pointer directly pointing to representative of x.But before that first we need to find the particular node containing element x among all the disjoint sets.so this searching is not O(1).I don't understand how Find_set(x) is O(1)(As given in books), when we don't know in which disjoint set the node containing x belongs.

Answer 1

Each element is assumed to contain some pointer/reference to the set it belongs to (the set can actually be represented by one of its member element). So when querying Find_Set(x), since you already have the element x, you simply have to consult this pointer/reference and the operation is O(1). With a linked-list implementation, where each set is stored as a linked list of elements, each element holds a pointer to the head of the linked list which is chosen as representative element of the set.