title: What data structure to use for the implementation of disjoint sets(union find)?
body: <p>Please note that this is not a homework question. I am training on Kattis and I came by a question that requires the use of Union-Find paradigms. Given the nature of the problem, I decided to implement my own UnionFind data structure. I understand that the interface of my DS should support:</p>
  
  <ol>
  <li>makeSet</li>
  <li>find(elem) -> returns reference to the representative of that set</li>
  <li>merge(firstElem, secondElem) -> merges the two parents of that set(also makes sure it is balanced)</li>
  </ol>
  
  <p>Now the issue is I am not implementing this data structure to support Integers which is usually implemented using an array where the index is the value and the representative of the set is always the value at that index. Instead my set contains strings and I am finding difficulty in choosing the data structure.</p>