union_find.h

#pragma once
 
#include <vector>
 
namespace cgv {
    namespace data {
 
struct union_find : public std::vector<unsigned int>
{
    union_find(unsigned int n) { init(n); }
    void init(unsigned int n) { 
        resize(n); 
        for (unsigned int i=0; i<n; ++i) 
            at(i) = i; 
    }
    unsigned int find(unsigned int i)
    {
        // find representative j
        unsigned int j = i;
        while (at(j) != j)
            j = at(j);
        // compress path
        while (i != j) {
            unsigned int tmp = at(i);
            at(i) = j;
            i = tmp;
        }
        return j;
    }
    void unify(unsigned int i, unsigned int j)
    {
        at(find(i)) = j;
    }
};
 
    }
}