dsf.c

   1 /*
   2  * dsf.c: two small functions to handle a disjoint set forest,
   3  * which is a data structure useful in any solver which has to
   4  * worry about avoiding closed loops.
   5  */
   6
   7 int dsf_canonify(int *dsf, int val)
   8 {
   9     int v2 = val;
  10
  11     while (dsf[val] != val)
  12         val = dsf[val];
  13
  14     while (v2 != val) {
  15         int tmp = dsf[v2];
  16         dsf[v2] = val;
  17         v2 = tmp;
  18     }
  19
  20     return val;
  21 }
  22
  23 void dsf_merge(int *dsf, int v1, int v2)
  24 {
  25     v1 = dsf_canonify(dsf, v1);
  26     v2 = dsf_canonify(dsf, v2);
  27     dsf[v2] = v1;
  28 }