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