flower/unionfind.hh

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