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 #include "puzzles.h"
   8
   9 int dsf_canonify(int *dsf, int val)
  10 {
  11     int v2 = val;
  12
  13     while (dsf[val] != val)
  14         val = dsf[val];
  15
  16     while (v2 != val) {
  17         int tmp = dsf[v2];
  18         dsf[v2] = val;
  19         v2 = tmp;
  20     }
  21
  22     return val;
  23 }
  24
  25 void dsf_merge(int *dsf, int v1, int v2)
  26 {
  27     v1 = dsf_canonify(dsf, v1);
  28     v2 = dsf_canonify(dsf, v2);
  29     dsf[v2] = v1;
  30 }
  31
  32 void dsf_init(int *dsf, int len)
  33 {
  34     int i;
  35
  36     for (i = 0; i < len; i++)
  37         dsf[i] = i;
  38 }