flower/include/unionfind.hh

   1 #ifndef UNIONFIND_HH
   2 #define UNIONFIND_HH
   3 #include "array.hh"
   4
   5 /*
   6     which points of a graph are connected?.
   7     Union find, a standard algorithm:
   8
   9     Union_find represents an undirected graph of N points. You can
  10     connect two points using #connect()#. #find (i)# finds a uniquely
  11     determined representant of the equivalence class of points
  12     connected to #i#.
  13
  14     */
  15 struct Union_find {
  16     void connect (int i, int j);
  17     int find (int i);
  18     bool equiv (int i, int j) { return find (i) == find (j); }
  19     Union_find (int sz);
  20
  21 private:
  22     Array<int> classes;
  23
  24 };
  25 #endif