flower/unionfind.hh

   1 #ifndef UNIONFIND_HH
   2 #define UNIONFIND_HH
   3 #include "varray.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