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 }