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   /**
  23      This array provides the representing point for each node in the graph.
  24    */
  25   Array<int> classes_;
  26 };
  27 #endif