#ifndef   DisjointSet_H__
#define   DisjointSet_H__

#include <vector>
#include <cstdlib>

namespace meow{
  class DisjointSet{
    private:
      size_t              n;
      std::vector<size_t> father;
      std::vector<size_t> depth;
      //
      size_t _root(size_t now);
      size_t _merge(size_t a, size_t b);
    public:
      DisjointSet();
      DisjointSet(size_t _n);
      DisjointSet(DisjointSet const& dsj);
      //
      size_t root (size_t a ) const;
      size_t size (         ) const;
      //
      void   reset(size_t _n         );
      size_t merge(size_t a, size_t b);
  };
  /*********************************************************
    @asciidoc
    === meow:: *DisjointSet* (C++ class)
    .Description
    `DisjointSet` is a lighting data structure that maintain N numbers from
    *0* to *N-1* with methods below:
    
   [options="header",width="100%",cols="1>,1<s,5<,1<,1<,10<",grid="rows"]
   |=======================================================================
   |Const?|Name| Parameters| Return Type| Time Complexity| Description
   |const|root|(size_t number)|size_t|very fast|
   Return the *group id* of the number given
   |const|size|()|size_t|very fast|
   Return *N*
   ||reset|(size_t N)|void|very fast|
   Clean and initalize
   ||merge|(size_t number1, +
   size_t number2)|size_t|very fast|
   *Union* the group contains number1 and the group contains number2.
   Return the merged group id
   |=======================================================================
NOTE: *very fast* means that you can consider it as constant time.

'''
@asciidoc-
   *********************************************************/
}

#include "DisjointSet.hpp"


#endif // DisjointSet_H__