title: Efficient way to find number of distinct elements in a list
body: <p>I'm trying to do K-Means Clustering using Kruskal's Minimum Spanning Tree Algorithm. My original design was to run the full-length Kruskal algorithm of the input and produce an MST, after which delete the last k-1 edges (or equivalently k-1 most expensive edges).</p>
  
  <p>Of course this is the same as running Kruskal algorithm and stopping it just before it adds its last k-1 edges.</p>
  
  <p>I want to use the second strategy i.e instead of running the full length Kruskal algorithm, stop it just after the number of clusters so far equals K. I'm using Union-Find data structure and using a list object in this Union-Find data structure.</p>
  
  <p>Each vertex on this graph is represented by its current cluster on this list e.g <code>[1,2,3...]</code> means vertices 1,2,3 are in their distinct independent clusters. If two vertices are joined  their corresponding indices on the list data structure are updated to reflect this.</p>
  
  <p>e.g merging vertices 2 and 3 leaves the list data object as <code>[1,2,2,4,5.....]</code></p>
  
  <p>My strategy is then every time two nodes are merged, count the number of DISTINCT elements in the list and if it equals the number of desired clusters, stop. My worry is that this may not be the most efficient option. Is there a way I could count the number of distinct objects in a list efficiently?</p>