0

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.

Tanmoy Banerjee
  • 1,433
  • 3
  • 22
  • 31
  • possible duplicate of [How to implement a Disjoint-set data structure by Linked list？](http://stackoverflow.com/questions/20797313/how-to-implement-a-disjoint-set-data-structure-by-linked-list) – Paul Hankin Jan 12 '14 at 16:03
  • 1
    this link does not contain proper answer to the question.they just provide the path comparison, not using list. – Tanmoy Banerjee Jan 12 '14 at 16:18

1 Answers1

0

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.

user3146587
  • 4,250
  • 1
  • 16
  • 25
  • "since you already have the element x".......my problem is there.initially I only know value of x but not the particular node.I have to search the sets to find the node first.how this searching can be done.after that,to find representative of that set simply have to consult the pointer/reference and the operation is O(1), which I understand. – Tanmoy Banerjee Jan 12 '14 at 15:34
  • @tan Could you give more context why you only have the values of the elements and not the elements themselves? That's probably what you have to fix in order to make the operations behave with their expected theoretical complexities. A quick'n dirty "fix" could be to maintain a hash map from value to node. – user3146587 Jan 12 '14 at 15:40
  • http://stackoverflow.com/questions/1243331/disjoint-set-as-linked-list there is a C++ program which implements the algorithm but as I don't know C++ I could not capture it. – Tanmoy Banerjee Jan 12 '14 at 15:43
  • 1
    @tan In the sample code posted as answer to the question you linked, the sets are actually represented by pointers to Item structures. These pointers are cast to/from long. Like I wrote above, any time an operation is done on an element (find for instance), you can retrieve the corresponding set from the element in constant time. You don't apply the find operation simply from a value that happens to be in the set. – user3146587 Jan 12 '14 at 15:53