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         classes[i] = i;
  12     }
  13 }
  14
  15 int
  16 Union_find::find(int i)
  17 {
  18     int rep = i;
  19     while (classes[rep] != rep)
  20         rep = classes[rep];
  21     while (classes[i] != rep) {
  22         int next =classes[i];
  23         classes[i] = rep;
  24         i = next;
  25     }
  26     return rep;
  27 }
  28
  29 void
  30 Union_find::connect(int i, int j)
  31 {
  32     i = find(i);
  33     j = find(j);
  34     classes[i] = j;
  35 }