UnionFind.h

#ifndef UNION_FIND_HEADER
#define UNION_FIND_HEADER

class UnionFind {
public:
    UnionFind(int N);
    ~UnionFind();

    int GetCount() const { return this->count; }

    int GetSize(int root) { return size[root]; }
    
    int Find(int p) const;

    bool Connected(int p, int q) const { return Find(p) == Find(q); }

    void Union(int p, int q);

private:
    int *parent;
    int *size;
    int count;
    int num;

    // Is this a valid index?
    inline bool Validate(int p) const;
};

#endif