flower/unionfind.cc

   1 #include "unionfind.hh"
   2 /*
   3   see a book on data structures
   4   */
   5
   6 Union_find::Union_find (int n)
   7 {
   8   classes.set_size (n);
   9
  10   for (int i=0; i < n; i++)
  11     {
  12         classes[i] = i;
  13     }
  14 }
  15
  16 int
  17 Union_find::find (int i)
  18 {
  19   int rep = i;
  20   while (classes[rep] != rep)
  21         rep = classes[rep];
  22   while (classes[i] != rep)
  23     {
  24         int next =classes[i];
  25         classes[i] = rep;
  26         i = next;
  27     }
  28   return rep;
  29 }
  30
  31 void
  32 Union_find::connect (int i, int j)
  33 {
  34   i = find (i);
  35   j = find (j);
  36   classes[i] = j;
  37 }